【Codeforces】B. Div Times Mod

B. Div Times Mod

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya likes to solve equations. Today he wants to solve $(x\ div\ k)⋅(x\ mod \ k)=n$, where divdiv and modmod 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?

Input

The first line contains two integers $n$ and $k$ ($1≤n≤10^6$, $2≤k≤1000$).

Output

Print a single integer $x$ — the smallest positive integer solution to $(x\ div\ k)⋅(x\ mod\ k)=n$. It is guaranteed that this equation has at least one positive integer solution.

Examples

input

Copy

6 3

output

Copy

input

Copy

1 2

output

Copy

input

Copy

4 6

output

Copy

Note

The result of integer division $a\ div\ b$ is equal to the largest integer $c$ such that $b⋅c≤a$. $a$ modulo $b$ (shortened $a\ mod\ b$) is the only integer $c$ such that $0≤c<b$, and $a−c$ is divisible by $b$.

In the first sample, $11\ div\ 3=3$ and $11\ mod\ 3=2$. Since $3⋅2=6$, then $x=11$ is a solution to $(x\ div\ 3)⋅(x\ mod\ 3)=6$. One can see that $19$ is the only other positive integer solution, hence $11$ is the smallest one.

题解：

数学题 ---- 我的致命弱点

由 $(x\ div\ k)·(x\ mod\ k) = n$ 可得， $(x\ mod\ k)$ 是 $n$ 的一个因数，则 n % $(x\ mod\ k)$ = 0，同样，n >= 1，所以 x != k 即不会 mod 得 0。

这样，我们就可以遍历 1 ~ k - 1 找 n % i == 0 的数，即 i == x mod k。同时这样也符合时间复杂度的范围。

得到 i == x mod k 后，可把 x div k 写成 $(x - i)\ /\ k$ （被除数、除数与余数的关系啦），这样式子就变成 ---- $(x - i)\ /\ k * i = n $ ，转换一下，得： $x = n\ /\ i\ *\ k + i$

需要注意一下是：题目要求输出最小的 $x$ ，所以要使 $x$ 最小，可以用 min()，但这里贪方便就直接从 k-1 开始查，这样就保证输出的定是最小的了。（除以一个正整数总比加上一个正整数要小得多吧？）

// https://codeforces.com/contest/1087/problem/B

#include<iostream>

#include<cstdio>

using namespace std;

int n, k;

int main()

{

    scanf("%d %d", &n, &k);

    for(int i = k - 1; i > 0; i--){

        if(n % i == 0){

            printf("%d\n", n / i * k + i);

            break;

        }

    }

    return 0;

}

巴特西

【Codeforces】B. Div Times Mod

B. Div Times Mod

最新文章

热门文章