題目來源:POJ 2480 Longge's problem
題意:求i從1到n的gcd(n, i)的和
思路:首先如果m, n 互質 gcd(i, n*m) = gcd(i, n)*gcd(i, m) 這是一個積性函數積性函數的和還是積性函數
由歐拉函數知識得 phi(p^a) = p^a - p^(a-1) p是素數 a是正整數
得到最終答案f(n) = f(p1^a1)*f(p2^a2)*...*f(pn^an) 其中f(p^a) = a*(p^a-p^(a-1))+p^a
#include#include #include #include using namespace std; typedef long long LL; const int maxn = 1000010; //篩素數 int vis[maxn]; LL prime[maxn]; LL pow_mod(LL a, LL p) { LL ans = 1; while(p) { if(p&1) { ans *= a; } a *= a; p >>= 1; } return ans; } void sieve(int n) { int m = sqrt(n+0.5); memset(vis, 0, sizeof(vis)); vis[0] = vis[1] = 1; for(int i = 2; i <= m; i++) if(!vis[i]) for(int j = i*i; j <= n; j += i) vis[j] = 1; } int get_primes(int n) { sieve(n); int c = 0; for(int i = 2; i <= n; i++) if(!vis[i]) prime[c++] = i; return c; } int main() { int c = get_primes(200000); int cas = 1; int T; LL n, ans; while(scanf("%I64d", &n) != EOF) { ans = 1; for(int i = 0; i < c && prime[i]*prime[i] <= n; i++) { if(n%prime[i] == 0) { LL sum = 0; while(n%prime[i] == 0) { sum++; n /= prime[i]; } ans *= sum*(pow_mod(prime[i], sum)-pow_mod(prime[i], sum-1))+pow_mod(prime[i], sum); } } if(n > 1) { ans *= n-1+n; } printf("%I64d\n", ans); } return 0; }