Cho n, k dương, tìm x dương thỏa (x % k)*(x / k) = n. Ví dụ n=4, k=6 → x=10 (10%6=4, 10/6=1, 4*1=4).
x%k ∈ [1, k-1]. Duyệt rem từ k-1 xuống 1, nếu n chia hết rem thì x = rem + (n/rem)*k, lấy min.
Ví dụ
#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); }
Kết quả
The minimum value of x: 10