题意

(n<=10⁶,k<=10⁸)

题解

一开始以为是搜索。

但想想不对，翻了一眼题解发现是欧拉函数。

因为

gcd(a,b)=gcd(a,a+b)

所以和n互质的数应该是类似a1,a2.....ax,a1+n,a2+n.....ax+n......这样的。

所以就可以瞎搞了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 int n,d,phi,c[1500000],tmp,ans,cnt; 8 int gcd(int x,int y){ 9     if(x==0)return y;10     if(y==0)return x;11     return gcd(y,x%y);12 }13 void get_phi(){14     for(int i=1;i<=n;i++){15         if(gcd(i,n)==1){16             phi++;17             c[++cnt]=i;18         }19     }20 }21 int main(){22     scanf("%d%d",&n,&d);23     get_phi();24     tmp=(d-1)/phi;25     ans=(d-1)%phi+1;26     printf("%d",c[ans]+tmp*n);27     return 0;28 }