根据欧几里德算法，gcd(a,b)=gcd(a+b*t,b)
如果a和b互质，则a+b*t和b也互质，即与a互质的数对a取模具有周期性。
所以只要求出小于n且与n互质的元素即可。
#include<stdio.h>
#include<string.h>
const int N=;
int pr[N],cnt;
int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
int main(){
int n,k;
while(~scanf("%d%d",&n,&k)){
cnt=;
for(int i=;i<=n;i++){
if(gcd(n,i)==)
pr[++cnt]=i;
}
if(k%cnt)
printf("%d\n",k/cnt*n+pr[k%cnt]);
else
printf("%d\n",(k/cnt-)*n+pr[cnt]);
}
return ;
}
也可以用欧拉函数求小于n且与n互质的元素。就不用O（N）了。速度提高10倍左右。