POJ 2480 - Longge's problem

http://poj.org/problem?id=2480

概要

自然数 N に対して Σgcd(i, N) 1 <= i <= N を答える．

制約

• 1 < N < 2^31

解法

gcd(i, N) = m であることと gcd(i/m, N/m) = 1 であることは同値であることを利用する．

すると gcd(i, N) = m となる i の個数は φ(N/m) に等しくなる． ここで φ は オイラーのφ関数．

よって N の約数 m について m * φ(N/m) の和が答えとなる．

約数の列挙も φ(N/m) の計算も O(sqrt(N)) でできるため，N < 2^31 でも大丈夫．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 long long phi(long long n)
 6 {
 7   long long ans = n;
 8   for (long long i = 2LL; i*i <= n; i++) {
 9     if (n % i == 0LL) {
10       ans -= ans / i;
11       while (n % i == 0LL) {
12         n /= i;
13       }
14     }
15   }
16   if (n > 1) {
17     ans -= ans / n;
18   }
19   return ans;
20 }
21 
22 vector<long long> factorize(long long n)
23 {
24   vector<long long> fs;
25   for (long long i = 1LL; i*i <= n; i++) {
26     if (n % i == 0LL) {
27       fs.push_back(i);
28       if (i*i != n) {
29         fs.push_back(n/i);
30       }
31     }
32   }
33   return fs;
34 }
35 int main()
36 {
37   long long N;
38   while (scanf("%lld", &N) != EOF) {
39     long long ans = 0;
40     const vector<long long> fs = factorize(N);
41     ans = 0;
42     for (vector<long long>::const_iterator it = fs.begin(); it != fs.end(); ++it) {
43       ans += *it * phi(N / *it);
44     }
45     printf("%lld\n", ans);
46   }
47   return 0;
48 }