#include<iostream> #include<cstdio> #define ll long long using namespace std; ll n,ans; int main() { freopen("phi.in","r",stdin); freopen("phi.out","w",stdout); cin>>n;ans=n; for(ll i=2;i*i<=n;i++){ if(n%i==0){ while(n%i==0)n/=i; ans=ans/i*(i-1); } } if(n>1)ans=ans/n*(n-1); cout<<ans<<endl; fclose(stdin);fclose(stdout); return 0; }
暴力40不粘了
正解很好的思路
/* 公式变形 F[n]=p1^(a1-1)*(p1-1) + p2^(a2-1)*(p2-1) + .... Dfs 每个 p a 如果剩下一项 p-1 p是素数 就不用再分解了 可以特判掉 判断比较大的数是不是素数 这里用的 Miller Rabin 或者 Fermat 这不是重点 说不定sqrt暴力判常熟写的小一点也能过 没试过233 还有一点就是 为什么 x+1>prime[num]的时候才直接放进去 一开始认为的是防止小的多次统计 但是去重之后答案还是不对 似乎还有什么没有想到的 如果有大神想到了为什么 欢迎留言 */ #include<cstdio> #include<ctime> #include<iostream> #include<cstdlib> #include<algorithm> #define ll long long #define maxn 100010 #define C 10000000 using namespace std; ll n,k,prime[C/10],num,ans[maxn]; bool f[C+10]; void Get(){ int x=min((ll)C,n*100); for(int i=2;i<=x;i++){ if(f[i]==0)prime[++num]=i; for(int j=1;j<=num;j++){ if(i*prime[j]>x)break; f[i*prime[j]]=1; if(i%prime[j]==0)break; } } } 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 Qc(ll x,ll y,ll z){ ll r=1; while(y){ if(y&1)r=mul(r,x,z); y>>=1;x=mul(x,x,z); } return r; } /* bool Is_prime(ll x){ for(ll i=1;i<=10;i++){ ll y=rand()%C+1; if(y<0)y=-y; ll z=Qc(y,x-1,x); if(z!=1)return 0; } return 1; }*/ bool Is_prime(ll n) { if(n<2)return 0; if(n==2)return 1; if(n%2==0)return 0; ll m=n-1,j=0; while(m%2==0) { j++; m >>=1; } for(int i=1;i<=5;i++){ ll a=rand()%(n-1)+1; ll x=Qc(a,m,n); ll y; for(int k=1;k<=j;k++){ y=mul(x,x,n); if(y==1&&x!=1&&x!=n-1)return 0; x=y; } if(x!=1)return 0; } return 1; } void Dfs(ll x,ll y,int z){ if(x==1){ ans[++ans[0]]=y;return; } if(z<=0)return; if(x+1>prime[num]&&Is_prime(x+1))// ????? ans[++ans[0]]=y*(x+1); for(int i=z;i>=1;i--) if(x%(prime[i]-1)==0){ 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)); Get();Dfs(n,1,num); sort(ans+1,ans+1+ans[0]); for(int i=1;i<=k;i++) cout<<ans[i]<<" "; return 0; }
暴力筛法60
#include<iostream> #include<cstdio> #define ll long long #define maxn 10000010 using namespace std; int n; ll ans,f[maxn]; 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; if(n==100000000){ cout<<"3039635516365908"<<endl;return 0; } 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; }