uva 11426 GCD

　　题意，求gcd(1,2)+gcd(1,3)+gcd(2,3)+...+gcd(n-1,n)的和。

　　这题的做法是，将gcd(a,b)=p(a<b)转化成gcd(a/p,b/p)=1，这时候就是求phi(b/p)，而且这样的值有p个。我用了类似筛素数的方法将所有的phi(x)都筛出来，同时计算gcd(1,n)+gcd(2,n)+...+gcd(n-1,n)的和。求出这个和以后，将之前的和加上去就行了。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 2222222;
 9 typedef long long LL;
10 int phi[N];
11 LL sum[N];
12 
13 void PRE() {
14     phi[1] = 1;
15     for (int i = 2; i < N; i++) {
16         if (!phi[i]) {
17             for (int j = i; j < N; j += i) {
18                 if (!phi[j]) phi[j] = j;
19                 phi[j] /= i;
20                 phi[j] *= i - 1;
21             }
22         }
23         for (int j = i; j < N; j += i) {
24             sum[j] += j / i * phi[i];
25         }
26         sum[i] += sum[i - 1];
27     }
28     //cout << sum[200000] << endl;
29     //cout << sum[100] << endl;
30     //cout << sum[10] << endl;
31 }
32 
33 int main() {
34     PRE();
35     int n;
36     while (cin >> n && n) cout << sum[n] << endl;
37     return 0;
38 }

View Code

——written by Lyon