题目链接

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 $\sum gcd$($i, N$) $1 \le i \le N$.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

输入格式

Input contain several test case.
A number $N$ per line.

输出格式

For each $N$, output ,$\sum gcd$($i,N$) $1 \le i \le N$, a line

样例输入

2
6

样例输出

3
15

题解

题目要求$\sum_{i=1}^ngcd$($i,n$)
那么我们考虑一个数$i$对答案的贡献,也就是$gcd$($k,n$)$==i$的个数乘上$i$。
首先,如果$i$不是$n$的因数,那么不可能有$gcd$($k,n$)$==i$,所以$i$对答案的贡献为$0$。
那么如果$i$是$n$的因子,那么如果存在$gcd$($k,n$)$==i$,那么$k$一定满足$k/i$和$n/i$互质,也就是说$k$和$n$的因子中除去$i$后没有相同的因子了。
那么我们马上就发现了$i$对答案的贡献就是$i*\phi$($n/i$)。
那么显然题目就变成了求$\sum_{i|n}i*\phi$($n/i$)

在判断质数的时候我们都学过一个数的因子都是“对称”的,所以在枚举$\phi$($n/i$)的过程中我们只要枚举到$\sqrt{n}$,就行了。

接下来的目标就是如何快速求$\phi$($i$)了,
我们先了解欧拉函数的一些性质:
有一个质数$p$,则
$\phi$($p^k$)$=p^k-p^{k-1}=p^{k-1}*(p-1)$
因为$p^k$以内不和$p^k$互质的数只有$p$的倍数,也就是数量为$\frac{p^k}{p}$
因为$\phi$是积性函数,所以令$p,k$互质,则
$\phi$($p*k$)$=\phi$($p$)$*\phi$($k$)
所以我们就能用下面的代码求$\phi$

inline long long phi(long long x){
    long long sum=x;
    for(long long j=2;j*j<=x;j++)
        if(x%j==0){
            while(x%j==0) x/=j;
            sum=sum/j*(j-1);
        }
    if(x!=1) sum=sum/x*(x-1);
    return sum;
}

ps:有多组数据
上代码:

#include<cstdio>
using namespace std;
long long n;
inline long long fd(long long x){
    long long sum=x;
    for(long long j=2;j*j<=x;j++){
        if(x%j==0){
            while(x%j==0) x/=j;
            sum=sum/j*(j-1);
        }
    }
    if(x!=1) sum=sum/x*(x-1);
    return sum;
}
long long sum;
int main(){
    while(scanf("%lld",&n)!=EOF){
        sum=0;
        for(long long i=1;i*i<=n;i++){
            if(n%i==0) sum+=fd(n/i)*i;
            long long u=n/i;
            if(u!=i && n%u==0) sum+=fd(n/u)*u;
        }
        printf("%lld\n",sum);
    }
    return 0;
}