我只是验证了一下公式而已,而已
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive Blog:http://willinglive.cf ************************************************/ #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) inline const int read() { int r=0,k=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1; for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0'; return k*r; } ///////////////////////////////////////////////// int n,x; int phi[1000000],prim[1000000],mu[1000000],cnt; bool flag[1000000]; ///////////////////////////////////////////////// int gcd(int a,int b){return b?gcd(b,a%b):a;} void get_prim_phi_mu() { cnt=0; MS(flag,0); mu[1]=1; rep(i,2,n) { if(!flag[i]) prim[++cnt]=i,phi[i]=i-1,mu[i]=-1; for(int j=1;j<=cnt && i*prim[j]<=n;j++) { flag[i*prim[j]]=1; if(i%prim[j]==0) { phi[i*prim[j]]=phi[i]*prim[j]; mu[i*prim[j]]=0; break; } else { phi[i*prim[j]]=phi[i]*(prim[j]-1); mu[i*prim[j]]=-mu[i]; } } } } ///////////////////////////////////////////////// void input() { scanf("%d%d",&n,&x); } void solve() { //暴力 O(nlogn) - O(nlogn) int ans=0; rep(i,1,x) { if(gcd(i,n)==1) ans++; } printf("%d\n",ans); //莫比乌斯 O(n) - O(sqrt(n)) get_prim_phi_mu(); ans=0; ans=phi[n]*(x/n); int t=x%n; int sq=sqrt(n); for(int d=1;d<=sq;d++) if(n%d==0) { ans+=t/d*mu[d]; if(d*d!=n) ans+=t/(n/d)*mu[n/d]; } printf("%d\n",ans); //上面纯属装逼,公式在这里 O(n) - O(sqrt(n)) get_prim_phi_mu(); ans=0; sq=sqrt(n); for(int d=1;d<=sq;d++) if(n%d==0) { ans+=x/d*mu[d]; if(d*d!=n) ans+=x/(n/d)*mu[n/d]; } printf("%d\n",ans); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(),solve(); return 0; }