在C++中查找满足(x % k) * (x / k) == n的最小x值

给定两个正整数n和k，我们需要找到一个正整数x，使得(x % k) * (x / k) 等于 n。例如，如果n和k分别为4和6，则输出为10，因为(10 % 6) * (10 / 6) = 4。

我们知道x % k的值在[1, k – 1]范围内（不包括0）。这里我们将找到该范围内能整除n的整数，因此给定的方程变为：x = (n * k) / (x % k) + (x % k)

示例

#include<iostream>
using namespace std;
int minValue(int x, int y){
   return (x > y)?y:x;
}
int getX(int n, int k) {
   int x = INT_MAX;
   for (int rem = k - 1; rem > 0; rem--) {
      if (n % rem == 0)
         x = minValue(x, rem + (n / rem) * k);
   }
   return x;
}
int main() {
   int n = 4, k = 6;
   cout << "The minimum value of x: " << getX(n, k);
}

输出

The minimum value of x: 10

Arnab Chakraborty

更新于：2019年12月18日

139 次浏览

开启您的职业生涯

完成课程获得认证

开始学习