根据欧几里德算法，gcd(a,b)=gcd(a+b*t,b)

如果a和b互质，则a+b*t和b也互质，即与a互质的数对a取模具有周期性。

所以只要求出小于n且与n互质的元素即可。

#include
     
      #include
      
       const int N=1000100;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=0;        for(int i=1;i<=n;i++){            if(gcd(n,i)==1)                pr[++cnt]=i;        }        if(k%cnt)            printf("%d\n",k/cnt*n+pr[k%cnt]);        else            printf("%d\n",(k/cnt-1)*n+pr[cnt]);    }    return 0;}
      
     

也可以用欧拉函数求小于n且与n互质的元素。就不用O（N）了。速度提高10倍左右。