hdu1695 莫比乌斯反演

莫比乌斯反演：可参考论文：《POI XIV Stage.1 《Queries》解题报告By Kwc-Oliver》

求莫比乌斯函数mu[i]：(kuangbin模板)

http://www.cnblogs.com/kuangbin/archive/2013/08/21/3273440.html

void Moblus()
{
    memset(check,false,sizeof(check));
    mu[1] = 1;
    int tot = 0;
    for(int i = 2; i <= MMX; i++)
    {
        if( !check[i] )
        {
            prime[tot++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < tot; j++)
        {
            if(i * prime[j] > MMX) break;
            check[i * prime[j]] = true;
            if( i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                break;
            }
            else
            {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}

本题题意：0<=x<=b，0<=y<=d，求满足gcd(x,y)=k这样的数对(x,y)的数量　　（(x,y)和(y,x)算一个）

参考论文提供的公式（自己推不粗来T^T），可以得出：

注意：这里得到的Ans是有序的，即(x,y)和(y,x)算两个

所以本题最终的结果应该是Result=G(b,d)-(G(b,b)/2)

画个图就能看出来：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 #define LL long long
 6 #define MMX 1000010
 7 #define mian main
 8 int mu[MMX];
 9 LL n;
10 bool check[MMX];
11 int prime[MMX];
12 
13 void Moblus()
14 {
15     memset(check,false,sizeof(check));
16     mu[1] = 1;
17     int tot = 0;
18     for(int i = 2; i <= MMX; i++)
19     {
20         if( !check[i] )
21         {
22             prime[tot++] = i;
23             mu[i] = -1;
24         }
25         for(int j = 0; j < tot; j++)
26         {
27             if(i * prime[j] > MMX) break;
28             check[i * prime[j]] = true;
29             if( i % prime[j] == 0)
30             {
31                 mu[i * prime[j]] = 0;
32                 break;
33             }
34             else
35             {
36                 mu[i * prime[j]] = -mu[i];
37             }
38         }
39     }
40 }
41 
42 int mian()
43 {
44     int T;
45     cin>>T;
46     Moblus();
47     for (int zy=1; zy<=T; zy++)
48     {
49         int a,b,c,d,k;
50         cin>>a>>b>>c>>d>>k;
51         if(k == 0)
52         {
53             cout<<"Case "<<zy<<": 0"<<endl;
54         }
55         else
56         {
57             if (b>d) swap(b,d);     //assume b<d
58             b=b/k;
59             d=d/k;
60 
61             LL ans1 = 0;
62             for(int i = 1; i <= b; i++)     //G(b,d)
63                 ans1 += (LL)mu[i]*(b/i)*(d/i);
64             LL ans2 = 0;
65             for(int i = 1; i <= b; i++)     //G(b,b)
66                 ans2 += (LL)mu[i]*(b/i)*(b/i);
67             ans1 -= ans2/2;
68 
69             cout<<"Case "<<zy<<": "<<ans1<<endl;
70         }
71     }
72 }

View Code

PS：还有用容斥原理做的，表示看不懂orz

http://blog.csdn.net/yang_7_46/article/details/9072533

http://blog.csdn.net/shiren_Bod/article/details/5787722