首页 > 代码库 > bzoj 2705: [SDOI2012]Longge的问题 歐拉函數
bzoj 2705: [SDOI2012]Longge的问题 歐拉函數
2705: [SDOI2012]Longge的问题
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 1035 Solved: 669
[Submit][Status]
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。
Source
枚舉n的因數k，算出gcd(i,n)==k,即gcd(i/k,n/k)==1，的數個數，即phi（n/k）。
這道題讓我意識到我思考問題的角度還是不夠廣，總是憑着第一感覺想下去，完全無法做到思路的變通。
以這道題爲例，我一看題，就認定這是莫比烏斯反演的題目，根本沒有思考其他的方式。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 1100000#define MAXV MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}qword n,m;qword prime[MAXN],topp=-1;bool pflag[MAXN];int gcd(int x,int y){ return (x%y==0) ? y : gcd(y,x%y);}void init(){ int i,j; for (i=2;i<MAXN;i++) { if (!pflag[i]) { prime[++topp]=i; } for (j=0;j<=topp && i*prime[j]<MAXN;j++) { pflag[i*prime[j]]=true; if (i%prime[j]==0) { break; } } }}qword phi(qword x){ int i; qword ret=1; for (i=0;i<=topp && prime[i]*prime[i]<=x;i++) { if(x%prime[i]==0) { ret*=prime[i]-1; x/=prime[i]; while (x%prime[i]==0) { ret*=prime[i]; x/=prime[i]; } } } if (x>1) { ret*=x-1; } return ret;}int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); qword i; scanf("%d",&n); qword ans1=0,ans2=0; // for (i=1;i<=n;i++) // ans1+=gcd(i,n); // printf("%d\n",ans1); init(); qword l=ceil(sqrt(n)); for (i=1;i*i<n;i++) { if (n%i==0) { ans2+=(qword)i*phi(n/i); ans2+=(qword)(n/i)*phi(i); } } if (l*l==n) { ans2+=(qword)(n/l)*phi(l); } printf(LL"\n",ans2); return 0;}
bzoj 2705: [SDOI2012]Longge的问题 歐拉函數
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。