题目描述：
分析：
根据欧几里德，我们有gcd（b×t+a，b）=gcd（a，b）
则如果a与b互质，则b×t+a与b也一定互质，如果a与b不互质，则b×t+a与b也一定不互质。
所以与m互质的数对m取模具有周期性，则根据这个方法我们就可以很快的求出第k个与m互质的数。
假设小于m的数且与m互质的数有l个，其中第i个是ai，则第k*l+i个与m互质的数是k*m+ai。
所以，我就for一遍求出所有m以内的与m互质的数，然后根据周期性求解。（感觉有点暴力对吧）
代码如下，很短的：
#include<cstdio>
#include<cstring>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 1000010
#define LL long long int p[Maxn],len; int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
} int main()
{
int m,k;
while(scanf("%d%d",&m,&k)!=EOF)
{
if(m==) {printf("%d\n",k);continue;}
len=;
for(int i=;i<=m;i++) if(gcd(i,m)==) p[++len]=i;
int ans;
if(k%len==) ans=(k/len-)*m+p[len];
else ans=k/len*m+p[k%len];
printf("%d\n",ans);
}
return ;
}
poj2773
2016-02-05 16:21:38