luogu P1592 互质（欧拉函数）

题意

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

题解

一开始以为是搜索。

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

因为

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

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

所以就可以瞎搞了。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,d,phi,c[],tmp,ans,cnt;

 int gcd(int x,int y){

     if(x==)return y;

     if(y==)return x;

     return gcd(y,x%y);

 }

 void get_phi(){

     for(int i=;i<=n;i++){

         if(gcd(i,n)==){

             phi++;

             c[++cnt]=i;

         }

     }

 }

 int main(){

     scanf("%d%d",&n,&d);

     get_phi();

     tmp=(d-)/phi;

     ans=(d-)%phi+;

     printf("%d",c[ans]+tmp*n);

     return ;

 }

巴特西

luogu P1592 互质（欧拉函数）

题意

题解

最新文章

热门文章