初体验==死活找不到错误在哪儿。

下面是题目复述：

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.

Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.

Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).

Output

Output the K-th element in a single line.

Sample

Input

2006 1

2006 2

2006 3

Output

1

3

5

下面是解题思路：

题目大意大概就是求m的第k个最大公约数为1的数字。特别的，答案可能比m要更大。

定理： 如果d/a和d/b均能整除，那么d/（a+b）也可以整除，d/（a * c1 + b * c2）也可以整除。（c1，c2均为常数。）

直接算出m以内的素数个数，m以外的数字仍呈周期性，然后根据gcd（m，a）=gcd（m * c+a，m）快速求出第k位上面的数字。

下面是AC代码：

#include <iostream>
#include <cstdio>
const int N=1e8;
using namespace std;
int gcd(int a,int b)//求最大公约数
{
    return b?gcd(b,a%b):a;
}
int prime[N];

int main()
{

    int m,k;
    while (scanf("%d%d",&m,&k)!=EOF)
    {
        int sum=0,ans;
        //if(n==1)printf("1\n");
        //else
        for(int i=1; i<=m; i++)
        {
            if(gcd(i,m)==1)
                prime[sum]=i,sum++;
        }
        if(k%sum) ans=k/sum*m+prime[k%sum-1];//看k在第几个m里面，然后找到对应m内的数字
        else ans=(k/sum-1)*m+prime[sum-1];//k%sum==0的时候，k在上一个轮回里面的最后一个数字
        printf("%d\n",ans);

    }
    return 0;
}