题目详情 - 第k个互质数 - 南阳理工学院OJ

ID: 817

远端评测题

1000ms

128MiB

难度: (无)

上传者:

两个数的a，b的gcd为1，即a，b互质，现在给你一个数m，你知道与它互质的第k个数是多少吗？与m互质的数按照升序排列。

Input

输入m ，k （1<=m<=1000000;1<=k<=100000000）

Output

输出第k个数。

Sample Input

10 1
10 2
10 3

Sample Output

1
3
7

HINT

Source