2705: [SDOI2012]Longge的问题
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 3325 Solved: 2082
[Submit][Status][Discuss]
Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。
与N的gcd结果一定是N的因子
那么我们枚举N的因子k，则ans = ∑k * f(k) ，f(k)表示小于N有多少个数gcd(i,N)=k
我们知道若gcd(i,N)=k，则gcd(i/k,N/k)=1，就变成了有多少个数与N/k互质，那不就是欧拉函数phi(N/k)么？
N <= 2^32，所以枚举N的因子最多不超过√N个，欧拉函数用质因数分解的求法是O(√(N / k))
总复杂度达不到O(N)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
LL phi(int n){LL ans = n,E = (int)sqrt(n);for (int i = 2; i <= E; i++){if (n % i == 0){ans = ans * (i - 1) / i;while (n % i == 0) n /= i;}}if (n - 1) ans = ans * (n - 1) / n;return ans;
}
int main()
{LL n,ans = 0;cin>>n;int E = (int)sqrt(n);for (int i = 1; i <= E; i++){if (n % i) continue;if (i * i == n) ans += i * phi(n / i);else ans += i * phi(n / i) + n / i * phi(i);}cout<<ans<<endl;return 0;
}