Longge's problem
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 6433 | Accepted: 2064 |
Description
Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.
"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.
Input
Input contain several test case.
A number N per line.
A number N per line.
Output
For each N, output ,∑gcd(i, N) 1<=i <=N, a line
Sample Input
2 6
Sample Output
3 15
Source
POJ Contest,Author:Mathematica@ZSU
题意:求 ∑gcd(i, N) 1<=i <=N
题解:涉及欧拉函数,积极函数,莫比乌斯反演等...本弱菜无法说明,搞了很久,但是代码非常短的说.....这大概就是典型的数论题的特征吧....
#include<stdio.h> int main() { long long n,temp,res,i,cou; while(scanf("%I64d",&n)>0) { for(res=1,i=2;i*i<=n;i++) { if(n%i!=0) continue; cou=0; temp=1; while(n%i==0){ n/=i; temp*=i; cou++; } res*=temp/i*(i-1)*cou+temp; } if(n>1) res*=2*n-1; printf("%I64d\n",res); } return 0; }