算法题：满足给定方程的最小正整数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#

//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

输出如下：

10

时间复杂度：O(n)

辅助空间：O(1)

---