Longge's problem（欧拉函数应用）

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

题目意思：给定一个数n,求1-n的所有数与这个数的gcd之和。
解题思路：先引入欧拉函数概念，φ(n) ：1到n-1有几个和x互质的数。
我们可以得知那些与n互质的数的gcd一定为1,也就是欧拉函数。而那些不与n互质的数gcd(i, n) = d ，d为n的约数。而这些约数必然是n的因子。

那么我们便可以想一想有没有什么方法可以直接将d相同的都找出来，我一瞬间想到的是筛法来筛去，但是筛法在面临很大的数的时候也会时间超限，所以需要换一种思路。我们会发现n的因子数很少啊，是不是可以直接去枚举因子呢？那么我就要判断gcd(i,n)中具有相同d的那些数，gcd(i,n)=d，i/d和n/d必须是互质的，也就是gcd(i/d,n/d)=1,而这个式子是什么？这就是求i/d和n/d互质的i在[1,n]里有几个，就等价于 1/d，2/d，...，n/d里面有几个和n/d互质，即φ(n/d)。接着求和约数为d的有φ(n/d)个，所以就是d*φ(n/d)，同时把约数为n/d的加上去，i*i==n特判一下。

以12为例：1,2,3,4,5,6,7,8,9,10,11,12。首先我们用欧拉函数将与12互质的1,5,7,11剔除，12特殊也剔除。这时候的ans=1+1+1+1+12=16。

这时候剩下2,3,4,6,8,9,10这些数与12的gcd没有计算。

接着我们枚举12的因子，ans+=2*eular(6) 2*2=4 （约数为2的有2个）

ans+=3*eular(4) 3*2=6 （约数为3的有2个）

ans+=4*eular(3) 4*2=8 （约数为4的有2个）

ans+=6*eular(2) 6*1=6 （约数为6的有1个）

完全和真实情况相同

原数：2,3,4,6,8,9,10

与12的公约数：2,3,4,6,4,3,2

是不是两个2，两个3，两个4，一个6？

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define ll long long int
 6 using namespace std;
 7 ll  eular(ll n)
 8 {
 9     ll i,ret=n;
10     for(i=2; i<=sqrt(n); i++)
11     {
12         if(n%i==0)
13         {
14             ret=ret/i*(i-1);
15             while(n%i==0)
16             {
17                 n/=i;
18             }
19         }
20     }
21     if(n>1)
22     {
23         ret=ret/n*(n-1);
24     }
25     return ret;
26 }
27 int main()
28 {
29     ll n,num,i,j;
30     ll ans;
31     while(scanf("%lld",&n)!=EOF)
32     {
33 
34         ans=eular(n)+n;
35         for(i=2;i<=sqrt(n);i++)
36         {
37             if(n%i==0)
38             {
39                 if(i*i==n)
40                 {
41                     ans=ans+eular(i)*i;
42                 }
43                 else
44                 {
45                     ans=ans+eular(i)*(n/i);
46                     ans=ans+eular(n/i)*i;
47                 }
48             }
49         }
50         printf("%lld
",ans);
51     }
52     return 0;
53 }