SPOJ 7001 VLATTICE

题目链接：http://www.spoj.com/problems/VLATTICE/

题意：求gcd(a, b, c) = 1 a,b,c <=N 的对数。

思路：我们令函数g(x)为gcd(a, b, c) = x的对数，那么这题就是要求g(1)。我们令f(x)为x | gcd(a, b, c)的对数，显然f(n) = sigma(n | d, g(d)) 。f(d) = (n/d) * (n/d) * (n/d)，那么我们就可以用莫比乌斯反演公式了， g(n) = sigma(n | d, mu(d/n)f(d)) g(1) = mu(d)f(d) = mu(d)*(n/d)*(n/d)*(n/d)。考虑1位为0，2位为0的情况。

莫比乌斯反演的两种形式：

g(n) = sigma(d | n, f(d)) f(n) = sigma(d | n, mu(d) * g(n/d))

g(n) = sigma(n | d, f(d)) f(n) = sigma(n | d, mu(d / n) * g(d))

code：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 typedef long long LL;
 5 const int MAXN = 1000005;
 6 bool check[MAXN];
 7 int primes[MAXN];
 8 int mu[MAXN];
 9 
10 void moblus()
11 {
12     memset(check, false, sizeof(check));
13     mu[1] = 1;
14     int cnt = 0;
15     for (int i = 2; i < MAXN; ++i) {
16         if (!check[i]) {
17             primes[cnt++] = i;
18             mu[i] = -1;
19         }
20         for (int j = 0; j < cnt; ++j) {
21             if (i * primes[j] > MAXN) break;
22             check[i * primes[j]] = true;
23             if (i % primes[j] == 0) {
24                 mu[i * primes[j]] = 0;
25                 break;
26             } else {
27                 mu[i * primes[j]] = -mu[i];
28             }
29         }
30     }
31 }
32 
33 int main()
34 {
35     moblus();
36     int nCase;
37     scanf("%d", &nCase);
38     while (nCase--) {
39         int n;
40         scanf("%d", &n);
41         LL ans = 3;        // 001 010 100
42         for (int i = 1; i <= n; ++i) {
43             ans += (LL)mu[i] * (n / i) * (n / i) * (n / i + 3);
44         }
45         printf("%lld
", ans);
46     }
47     return 0;
48 }