Div Times Mod
Hazrat Ali
Vasya likes to solve equations. Today he wants to solve (x div k)⋅(xmodk)=n, where div and mod stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, k and n are positive integer parameters, and x is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible x. Can you help him?
The first line contains two integers n and k (1≤n≤106, 2≤k≤1000).
Print a single integer x — the smallest positive integer solution to (x div k)⋅(xmodk)=n. It is guaranteed that this equation has at least one positive integer solution.
6 3
11
1 2
3
4 6
10
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> ans;
for (int i = 1; i < k; i++)
{
if (n % i == 0)
{
int x = i;
while (true)
{
if (x / k * (x % k) == n)
{
ans.push_back(x);
break;
}
x += k;
}
}
}
sort(ans.begin(), ans.end());
cout << ans[0] << endl;
return 0;
}