【SDOI2012】bzoj2705 Longge的问题_综合

Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i
<=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。

\sum i = 1 n gcd (i, n) = \sum i = 1 n \sum d ∣ gcd (i, n) φ (d) = \sum i = 1 n \sum d ∣ i \land d ∣ n φ (d) = \sum d ∣ n φ (d) ? d n

$\begin{align} & \sum_{i=1}^n \gcd(i,n)\\& =\sum_{i=1}^n \sum_{d\mid\gcd(i,n)} \varphi(d)\\ & = \sum_{i=1}^n \sum_{d\mid i\land d\mid n}\varphi(d)\\& = \sum_{d\mid n} \varphi(d) * \frac dn \end{align}$

枚举n的因数，再计算欧拉函数求和。

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