题目描述
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
输入输出格式
输入格式：
一个整数，为N。
输出格式：
一个整数，为所求的答案。
输入输出样例
输入样例#1：
6
输出样例#1：
15
说明
对于60%的数据，0<N<=2^16
对于100%的数据，0<N<=2^32
Solution：
本题数学。
设$f(x)$表示范围内$gcd(i,j)=x$的数的个数，则$f(x)=\sum_\limits{i=1}^{i\leq n}{(gcd(i,n)=x)}\;=\;\sum_\limits{i=1}^{i\leq \frac{n}{x}}{x*(gcd(i,\frac{n}{x})=1)}\;=\;x*\varphi (\frac{n}{x})$。
所以原式$=\sum_\limits{i|n}^{i\leq n}{i*\varphi (\frac{n}{i})}$。
于是直接暴力根号枚举n的因子，然后暴力根号筛$\varphi$ 求解就好了，时间复杂度$O(n^{\frac{3}{4}})$（注意开long long，被坑惨了）。
代码：
/*Code by 520 -- 9.20*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
ll n;
ll ans; ll phi(ll x){
ll ans=x;
for(ll i=;i*i<=x;i++)
if(x%i==) {
while(x%i==) x/=i;
ans=ans/i*(i-);
}
if(x>) ans=ans/x*(x-);
return ans;
} int main(){
cin>>n;
ll i=;
for(i=;i*i<n;i++)
if(n%i==) ans+=i*phi(n/i)+(n/i)*phi(i);
if(i*i==n) ans+=i*phi(i);
cout<<ans;
return ;
}