莫比乌斯反演

资料 http://wenku.baidu.com/view/542961fdba0d4a7302763ad5.html

还有一些就看百度百科或者其他人的blog。并不是很懂

POJ 3090是二维的，这个是三维版本。二维的可以用欧拉函数做。三维用莫比乌斯反演做，具体解释看这里。我并没有很懂，感觉莫比乌斯反演好牛逼啊

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 1000100
15 
16 bool check[mnx];
17 int mu[mnx], tot, prime[mnx];
18 void init(){
19     mu[1] = 1;
20     for( int i = 2; i < mnx; ++i ){
21         if( !check[i] )
22             prime[tot++] = i, mu[i] = -1;
23         for( int j = 0; i * prime[j] < mnx &&j < tot; ++j ){
24             check[i*prime[j]] = 1;
25             if( i % prime[j] == 0 ){
26                 mu[i*prime[j]] = 0;
27                 break;
28             }
29             else mu[i*prime[j]] = -mu[i];
30         }
31     }
32 }
33 int main(){
34     int cas;
35     scanf( "%d", &cas );
36     init();
37     while( cas-- ){
38         int n;
39         scanf( "%d", &n );
40         LL ans = 0;
41         for( int i = 1; i <= n; ++i )
42             ans += (LL)mu[i] * (n/i) * (n/i) * (n/i+3); //(+3是指x-y, x-z, y-z三个平面)
43         printf( "%lld
", ans + 3 );
44     }
45     return 0;
46 }

View Code

HDU 1695 GCD

做了上题，这题就没什么难度了。已经用容斥搞过了，不过容斥比莫比乌斯反演慢很多。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define LL long long
11 #define eps 1e-8
12 #define lson l, m, rt<<1
13 #define rson m+1, r, rt<<1|1
14 #define mnx 100100
15 
16 bool check[mnx];
17 int mu[mnx], tot, prime[mnx];
18 void init(){
19     mu[1] = 1;
20     for( int i = 2; i < mnx; ++i ){
21         if( !check[i] )
22             prime[tot++] = i, mu[i] = -1;
23         for( int j = 0; i * prime[j] < mnx &&j < tot; ++j ){
24             check[i*prime[j]] = 1;
25             if( i % prime[j] == 0 ){
26                 mu[i*prime[j]] = 0;
27                 break;
28             }
29             else mu[i*prime[j]] = -mu[i];
30         }
31     }
32 }
33 int main(){
34     int cas, kk = 1;
35     scanf( "%d", &cas );
36     init();
37     while( cas-- ){
38         LL n, m, nn, mm, k;
39         scanf( "%I64d%I64d%I64d%I64d%I64d", &nn, &n, &mm, &m, &k );
40         if( k == 0 ){
41             printf( "Case %d: 0
", kk++ ); continue ;
42         }
43         n /= k, m /= k;
44         if( n > m ) swap( n, m );
45         LL ans = 0, ans1 = 0;
46         for( int i = 1; i <= n; ++i )
47             ans += (LL)mu[i] * (n/i) * (m/i);
48         for( int i = 1; i <= n; ++i )
49             ans1 += (LL)mu[i] * (n/i) * (n/i);
50         printf( "Case %d: %I64d
", kk++, ans - ans1/2 );
51     }
52     return 0;
53 }

View Code

HYSBZ 2301 Problem b

中文题。对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k。

上题已经做了1 <= x <= b，1 <= y <= d，且gcd( x, y ) = k的。因此，对a <= x <= b, c <= y <= d，可以用容斥搞。ans = calc( b, d ) - calc( a-1, d ) - calc( b, c-1 ) + calc( a-1, c-1 );但是题目有5w组case，每组case都是O(n)的复杂度，会tle，因此还需要再优化。用分块的方法，因为对于一段区间，( L / i ), ( R / i )的值可能是一样的。所以我们先预处理莫比乌斯函数的前缀和，然后对于i，令j = min( L/(L/i), R/(R/i) )，区间 [ i，j ]的商都是一样的，所以ret += (s[j] - s[i-1] ) * (L/i) * (R/i);这样处理后复杂度的O(sqrt(n))，5w组case就可以过了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <queue>
 8 
 9 using namespace std;
10 
11 #define LL long long
12 #define eps 1e-8
13 #define pb push_back
14 #define pf push_front
15 #define lson l, m, rt<<1
16 #define rson m+1, r, rt<<1|1
17 #define mnx 51000
18 
19 bool check[mnx];
20 int mu[mnx], tot, prime[mnx], s[mnx];
21 void init(){
22     mu[1] = 1;
23     for( int i = 2; i < mnx; ++i ){
24         if( !check[i] )
25             prime[tot++] = i, mu[i] = -1;
26         for( int j = 0; j < tot && i * prime[j] < mnx; ++j ){
27             check[i*prime[j]] = 1;
28             if( i % prime[j] == 0 ){
29                 mu[i*prime[j]] = 0;
30                 break;
31             }
32             else mu[i*prime[j]] = -mu[i];
33         }
34     }
35     for( int i = 1; i < mnx; ++i )
36         s[i] = s[i-1] + mu[i];
37 }
38 int a, b, c, d, k;
39 LL calc( int L, int R ){
40     L /= k, R /= k;
41     LL ret = 0;
42     if( L == 0 || R == 0 ) return 0;
43     if( L > R ) swap( L, R );
44     for( int i = 1, j; i <= L; i = j+1 ){
45         j = min( L/(L/i), R/(R/i) );
46         ret += (LL)( s[j] - s[i-1] ) * ( L/i ) * ( R/i );
47     }
48     return ret;
49 }
50 int main(){
51     init();
52     int cas;
53     scanf( "%d", &cas );
54     while( cas-- ){
55         scanf( "%d%d%d%d%d", &a, &b, &c, &d, &k );
56         LL ans = calc( b, d ) - calc( a-1, d ) - calc( b, c-1 ) + calc( a-1, c-1 );
57         printf( "%lld
", ans );
58     }
59     return 0;
60 }

View Code