题目连接：

题意：求gcd(x, y) = 1,  0 <= x, y <= n的对数

思路：这题范围是从0开始的，所以，会多出(1, 0)和(0, 1)这两组，答案就是sigma(phi(i)) - 1 + 2。

code：

1 #include 
     
       2 #include 
      
        3 typedef long long LL; 4 const int MAXN = 100005; 5  6 LL phi[MAXN]; 7 int primes[MAXN]; 8 bool is[MAXN]; 9 int cnt;10 11 12 void init()13 {14     phi[1] = 1L;15     cnt = 0;16     memset(is, false, sizeof(is));17     for (int i = 2; i < MAXN; ++i) {18         if (!is[i]) {19             primes[cnt++] = i;20             phi[i] = i - 1;21         }22         for (int j = 0; j < cnt && i * primes[j] < MAXN; ++j) {23             is[i * primes[j]] = true;24             if (i % primes[j] == 0) phi[i * primes[j]] = phi[i] * primes[j];25             else phi[i * primes[j]] = phi[i] * (primes[j] - 1);26         }27     }28 }29 30 int main()31 {32     init();33     int n;34     while (scanf("%d", &n) != EOF) {35         LL ans = 0;36         --n;37         for (int i = 2; i <= n; ++i) phi[i] += phi[i - 1]; 38         ans += phi[n] * 2 + 1;39         printf("%lld\n", ans);40     }41     return 0;42 }