/* φ(n)=φ(p^k)=p^k-p^(k-1)=(p-1)*p^(k-1) φ(m*n)=φ(m)*φ(n) 直接套公式做，因为分解质因数时，只分解一个数，所以可以不打素数表，只将n分解到√n就行了。 */ #include<iostream> #include<cstdio> #define ll long long #define N 1000010LL using namespace std; ll prime[N],c[N],P[N],f[N],num,n; ll poww(ll a,ll b) { ll base=a,r=1; while(b) { if(b&1)r*=base; base*=base; b/=2; } return r; } int main() { freopen("phi.in","r",stdin); freopen("phi.out","w",stdout); cin>>n; for(ll i=2;i<=min(n,N-1);i++) { if(!f[i]) { prime[++num]=i;P[i]=num; for(ll j=2;i*j<=min(n,N-1);j++) f[i*j]=1; } } ll x=n; for(ll i=1;i<=num;i++) { ll p=prime[i]; while(x%p==0)c[i]++,x/=p; if(x<N)if(!f[x]) { c[P[x]]++;break; } if(x==1)break; } ll ans=1; for(ll i=1;i<=num;i++) if(c[i])ans*=(prime[i]-1)*poww(prime[i],c[i]-1); if(x>N)ans*=(x-1); cout<<ans; fclose(stdin); fclose(stdout); return 0; }
/* φ(n)=φ(p1^k1+p2^k2……)=(p1-1)p1^k1-1+……=m 利用公式反推：从大到小枚举素数。 */ #include<cstdio> #include<iostream> #include<ctime> #include<cstdlib> #include<algorithm> #define N 10000010 #define ll long long using namespace std; bool f[N];ll n,k,prime[N/10],num,ans[N/10]; void gprime() { for(ll i=2;i<=N-10;i++) { if(!f[i])prime[++num]=i; for(ll j=1;j<=num;j++) { if(i*prime[j]>N-10)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } ll gcd(ll a,ll b) { if(b==0)return a; return gcd(b,a%b); } ll mul(ll x,ll y,ll z) { ll r=0; while(y) { if(y&1)r+=x,r%=z,y--; x<<=1;x%=z;y>>=1; } return r; } ll poww(ll a,ll b,ll mod) { ll base=a,r=1; while(b) { if(b&1)r=mul(r,base,mod); base=mul(base,base,mod); b>>=1; } return r; } bool is_prime(ll x)//费马小定理判断素数 { for(ll i=1;i<=5;i++) { ll y=rand()%(N-10)+1; if(y<0)y=y-y; ll z=poww(y,x-1,x); if(z!=1)return false; } return true; } void dfs(ll x,ll y,ll z) { if(x==1) { ans[++ans[0]]=y;return; } if(x+1>prime[num]&&is_prime(x+1)) ans[++ans[0]]=y*(x+1); for(ll i=z;i>=1;i--) { if(x%(prime[i]-1)!=0)continue; ll a=x/(prime[i]-1),b=y,c=1; while(a%c==0) { b*=prime[i];dfs(a/c,b,i-1);c*=prime[i]; } } } int main() { freopen("arc.in","r",stdin); freopen("arc.out","w",stdout); cin>>n>>k; srand(time(0)); gprime();dfs(n,1,num); sort(ans+1,ans+ans[0]+1); for(ll i=1;i<=k;i++) cout<<ans[i]<<" "; return 0; }
/*筛法求欧拉函数*/ #include<iostream> #include<cstdio> #define ll long long #define N 10000010 using namespace std; int n; ll ans,f[N]; void X(ll x) { for(int i=1;i<=x;i++)f[i]=i; for(int i=2;i<=x/2;i++) { if(f[i]==i) { for(int j=i;j<=x;j+=i) { f[j]=f[j]*(i-1)/i; } } } } int main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); cin>>n; X(n);ans=1; for(int i=2;i<=n;i++) { if(f[i]==i)f[i]--; ans+=f[i]; } cout<<ans<<endl; fclose(stdin);fclose(stdout); return 0; }