POJ_2480 Longge's problem【积性函数+欧拉函数的理解与应用】

题目：

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

题意分析：

做这题前，首先要对两个概念有一定的理解，积性函数和欧拉函数，浅层次的了解是无法推导出最终答案的，只有深入理解。（这完全是屁话- -！）

分析gcd是积性函数,当a,b互质时，易证

$gcd(a imes b,N) = gcd(a,N) imes gcd(b,N)$

这样，我们也可以得出

$f(N) = sum_{i=1}^{N}gcd(i,N)$

也是积性函数。

然后我们分析N，如果一个数t，它与N的最大公约数2，即gcd(t,N)=2.那么我们可以得出

$gcd(t/2,N/2) = 1$

有没有发现什么，如果没有，回想欧拉函数的性质φ(N/2)的意义是不超过N/2的所有与N/2互素的数的数量。而这些与N/2互素的数字其实就是所有满足上述条件的t/2，再结合题目，那么φ(N/2)就是所有满足gcd(i,N)=2条件的数的数目。再乘以2就是这些数的和。3, 4, 5, ……依此类推。

现在我们往特殊的情况考虑，假设N是素数p。则

$f(p) = varphi (p)$

那么当N为p^r次方时,N的与i的最大公约数的值可能有1，p，p^2，……，p^r.

$f(p^r) =1 imes varphi(p^r/1)+p imes varphi(p^r/p)+cdots +p^{r-1} imesvarphi(p^r/p^r-1)+p^r imes varphi(p^r/p^r)$

思路有没有变明朗呢？如果没有，那只能原谅我语文确实是体育老师教的。QAQ

直接拿出大招搞事了。

根据上述的公式，然后结合当为奇数次幂时的欧拉函数公式，直接推出

$f(p^r) =r(p^r-p^{r-1})+p^r$

不得不吐槽下自己，自己在写代码时，因为装*，这个式子我又转换了一下，结果一直WA。看来还是要一步一步来啊。

接下来，玩玩拆数字游戏了，根据素数分解，把N分解成素数分解成素数幂相乘，再根据积性函数性质+上述推导的公式，最终结果就是答案了。写的时候注意下控制long long就可以了。

$N=p_1^{r_1} imes p_2^{r_2} imes cdots imes p_k^{r_k}$

$f(N)=f(p_{1}^{r_1}) imes f(p_{2}^{r_2}) imes cdots imes f(p_{k}^{r_k})$

终于over了。

可以用素数打表再写（47ms)，但是估计数据不多，直接试除速度更快(32ms)。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;


void solve(LL N)
{
    LL ans = 1;
    for(LL i = 2; i*i <= N; i++)
    {
        if(N%i==0)
        {
            LL r = 0;
            LL t = 1;
            do
            {
                N/=i;
                r++;
                t*=i;
            }while(N%i==0);
            ans*=(r + 1) * t - t / i * r;
        }
    }
    if(N>1)
    {
        ans*=2*N-1;
    }
    printf("%I64d
", ans);
}

int main()
{
    LL N;
    while(scanf("%I64d", &N) != EOF)
    {
        solve(N);
    }
    return 0;
}