#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL n,ans; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { freopen("phi.in","r",stdin); freopen("phi.out","w",stdout); n=init();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; }
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<cstdlib> #include<algorithm> #define LL long long #define maxn 10000000 using namespace std; LL n,w,tot,topt; LL prime[maxn],f[maxn],ans[maxn]; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void prepare() { for(LL i=2;i<=10000000;i++) { if(!f[i])prime[++tot]=i; for(LL j=1;j<=tot&&prime[j]*i<=10000000;j++) { f[prime[j]*i]=1; if(i%prime[j]==0)break; } } } LL slow_mul(LL a,LL b,LL p) { LL ret=0; while(b) { if(b&1)b--,ret+=a,ret%=p; a<<=1;a%=p;b>>=1; } return ret; } LL pow(LL x,LL q,LL p) { if(q==0)return 1; LL ha=pow(x,q/2,p); ha=slow_mul(ha,ha,p); if(q&1)ha=slow_mul(ha,x,p); return ha; } LL judge(LL x) { LL flag=0; for(LL i=1;i<=5;i++) { LL s=rand(); if(pow(s,x-1,x)==1)continue; flag=1;break; } return flag==0; } void dfs(LL x,LL rest,LL sum) { if(rest==1) { ans[++topt]=sum; return; } if(rest+1>prime[tot]&&judge(rest+1)) ans[++topt]=sum*(rest+1); for(int i=x;i>=1;i--) { if(rest%(prime[i]-1)==0) { LL r=rest,s=sum; while(1) { s*=prime[i]; dfs(i-1,r/(prime[i]-1),s); if(r%prime[i]!=0)break; r/=prime[i]; } } } } int main() { freopen("arc.in","r",stdin); freopen("arc.out","w",stdout); srand(time(0)); n=init();w=init(); prepare(); dfs(tot,n,1); sort(ans+1,ans+topt+1); //unique(ans+1,ans+topt+1); for(LL i=1;i<=w;i++) cout<<ans[i]<<" "; return 0; }
暂无正解
60分代码:
/* 60分 */ #include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; LL n,ans,f[10000010]; LL init() { LL x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void prepare() { f[1]=1; for(LL i=2;i<=n;i++) { if(!f[i]) { f[i]=i-1; for(LL j=i*2;j<=n;j+=i) { if(!f[j])f[j]=j; f[j]=f[j]/i*(i-1); } } } } int main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); n=init(); prepare(); for(LL i=1;i<=n;i++) ans+=f[i]; cout<<ans<<endl; return 0; }