输入两个正整数n和k，求与n互质的第k个正整数。
输入格式：
仅一行，为两个正整数n(≤10^6)和k(≤10^8)。
输出格式：
一个正整数，表示与n互质的第k个正整数。
10 5
11
#include<cstdio> int a[1000006]; int gcd(int x,int y) { if(y==0)return x; else return gcd(y,x%y); } int main() { int n,k,num=0; scanf("%d%d",&n,&k); a[0]=n-1; for(int i=1;i<n;++i) if(gcd(i,n)==1)a[++num]=i; printf("%d\n",(k-1)/num*n+a[k%num]); return 0; }
原文：http://www.cnblogs.com/sssy/p/7147331.html