POJ2480 Longge's problem

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7994		Accepted: 2650

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.

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

和BZOJ2705一样的题……

本来觉着把之前的代码复制过来稍微改改就能过了，然而做不到！

各种TLE！

把能想到的优化都堆上去了，好不容易才AC。

POJ数据是有多猛……

 1 /*by SilverN*/
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 inline long long phi(long long x){
 9     long long a=x;
10     long long m=sqrt(x+0.5);
11     for(long long i=2;i<=m;i++){
12         if(x%i==0){//找到因数 
13             a=a/i*(i-1);//基本计算公式 a*=((i-1)/i) 
14             while(x%i==0)x/=i;//除去所有相同因数 
15         }
16     }
17     if(x>1)a=a/x*(x-1);//处理最后一个大因数 
18     return a;
19 }
20 int main(){
21     long long n;
22     while(~scanf("%lld",&n)){
23         long long ans=0;
24         long long m;
25         m=floor(sqrt(1.0*n));
26         long long i;
27         for(i=1;i<=m;++i){
28             if(n%i==0){
29                 ans+=(long long)phi(n/i)*i;
30                 if(i*i<n)ans+=(long long)(n/i)*phi(i);
31             }
32         }
33         printf("%lld
",ans);
34     }
35     return 0;
36 }