[jzoj 1164] 求和 {欧拉函数}

题目

Description
若两个数的最大公约数为1，则这两个数互质。现在给出一个正整数N（1<=2^31-1)，你的任务是求出1~N中与N互质的数的总和。
Input
一个整数N
Output
一个整数sum，表示1~N中与N互质的数的总和。

---

解题思路

ans=N∗φ(N)/2$ans=N\ast \phi (N)/2$
至于为什么，请看下面的证明（真心很难看懂）：

---

代码

#include<cstdio>
#include<cmath>
using namespace std; 
long long n; 
int phi(long long n)
{
    long long ans=n; 
    for (long long i=2;i<=sqrt(n);i++)
     if (n%i==0) {
        ans=ans/i*(i-1); 
        while (n%i==0) n/=i; 
     }
    if (n>1) ans=ans/n*(n-1); 
    return ans; 
}
int main()
{
    scanf("%lld",&n); 
    printf("%lld",phi(n)*n/2); 
}