算法题（满足给定方程的最小正整数X） _数据结构

本文概述

C ++
Java
Python3
C#

给定两个整数N和K，任务是找到满足方程的最小正整数X:

(X/K)*(X%K)= N

例子：

输入：N = 6, K = 3
输出：11
说明：
对于X = 11, (11/3)*(11％3)= 3 * 2 = 6
因此, 下式满足。
输入：N = 4, K = 6
输出：10
说明：
对于X = 10, (10/6)*(10％6)= 1 * 4 = 4
因此, 下式满足。

方法：
其思想是，由于(X / K) * (X % K) = N，因此N能被p = X % K整除，而p = X % K小于K。因此，对于[1,K]范围内的所有i，尝试p的所有值，其中:
下面是上述方法的实现：
C ++

//C++ Program to implement //the above approach #include < bits/stdc++.h> using namespace std; //Function to find out the smallest //positive integer for the equation int findMinSoln( int n, int k) { //Stores the minimum int minSoln = INT_MAX; //Iterate till K for ( int i = 1; i < k; i++) {//Check if n is divisible by i if (n % i == 0) minSoln = min(minSoln, (n /i) * k + i); }//Return the answer return minSoln; }//Driver Code int main() { int n = 4, k = 6; cout < < findMinSoln(n, k); }

Java

//Java Program to implement //the above approach import java.util.*; class GFG{//Function to find out the smallest //positive integer for the equation static int findMinSoln( int n, int k) { //Stores the minimum int minSoln = Integer.MAX_VALUE; //Iterate till K for ( int i = 1 ; i < k; i++) {//Check if n is divisible by i if (n % i == 0 ) minSoln = Math.min(minSoln, (n /i) * k + i); }//Return the answer return minSoln; }//Driver Code public static void main(String[] args) { int n = 4 , k = 6 ; System.out.println(findMinSoln(n, k)); } }//This code is contributed by Ritik Bansal

Python3

# Python3 program to implement # the above approach import sys# Function to find out the smallest # positive integer for the equation def findMinSoln(n, k):# Stores the minimum minSoln = sys.maxsize; # Iterate till K for i in range ( 1 , k):# Check if n is divisible by i if (n % i = = 0 ): minSoln = min (minSoln, (n //i) * k + i); # Return the answer return minSoln; # Driver Code if __name__ = = '__main__' :n = 4 ; k = 6 ; print (findMinSoln(n, k)); # This code is contributed by amal kumar choubey

//C# program to implement //the above approach using System; class GFG{//Function to find out the smallest //positive integer for the equation static int findMinSoln( int n, int k) {//Stores the minimum int minSoln = int .MaxValue; //Iterate till K for ( int i = 1; i < k; i++) {//Check if n is divisible by i if (n % i == 0) minSoln = Math.Min(minSoln, (n /i) * k + i); }//Return the answer return minSoln; }//Driver Code public static void Main(String[] args) { int n = 4, k = 6; Console.WriteLine(findMinSoln(n, k)); } }//This code is contributed by amal kumar choubey

输出如下：