GCD問題--莫比烏斯反演

GCD問題

Time Limit: 1000ms   Memory limit: 65536K  有疑問？點這裡^_^

題目描述

給出區間 gcd(x,y) = k,a <=x <= b,c <= y <= d 。T(1 <= T <= 100).T行，每行五個整數

輸出

輸出

示例輸入

2
384 31270 278 37299 70
336 35722 493 16985 158      

示例輸出

141647
14170      

題目連結：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=3320

很水的一個反演，不過我很高興，自從下定決心來幹掉反演之後這是做出來的第一個反演的題，已經卡了我3天了，我此刻的心情隻能用一串中文字元來表達，哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈......爽！

我的反演是看百科懂的，很神奇吧，順着百科推一遍你就回得到f(x)和g(x)的關系了。當然，我還隻是個反演小白，本質沒有變化。

http://baike.baidu.com/link?url=W9FfzhfR_QWTX7lCjjhh-0-bm2rP4mF6zwFoEFZGyws3GcS9QkZ_fleL02tDmuBaZzFZbjK0WK7VmCdUqBRpv_

這是百科的連結，有感興趣的可以去學一下，以前看不懂金桔的部落格，現在發現寫的還挺對，辛苦他打這麼多字了，既然如此，我隻好http://blog.csdn.net/a1s4z5/article/details/51333840，嘿嘿嘿嘿嘿。

講的很好，第二部分我到現在也沒有懂。。。其實說白了，莫比烏斯反演就是一個偏序集上的容斥，u(x)就是容斥系數，其實u(x)就是個歐拉函數，是以，強烈建議先去學前置技能。

1.容斥原理

2.唯一分解定理

3.歐拉函數定義

4.積性函數定義

容斥的話我是上知乎學的，哦，還有組合數學那本書，唯一分解定理也是在百科，我記得好像文庫裡面有篇論文，裡面有唯一分解定理的應用，但是并沒有看懂多少。。。畢竟渣，歐拉函數和積性函數我到現在也隻是知道結論，不過對于我們來說知道結論也夠了。

在這裡，我一定要放上莫比烏斯反演的兩種形式

形式一

如果有  f(n)=∑d|ng(d)  

那麼  g(n)=∑d|nμ(d)f(nd)

形式二

如果有  f(n)=∑n|dg(d)  

那麼  g(n)=∑n|dμ(dn)f(d)

證明的話是用卷積證明（乘法），至于必要性和充分性在百科上有，我在此就不證了，淡定！

形式一是約數關系，形式二是倍數關系。

u(x)函數的求法這裡我用的是線性篩，金桔的5行闆子的水準我還達不到。

http://blog.csdn.net/acdreamers/article/details/8542292

大神的闆子，我看了好多部落格，ACdreamr寫的還不錯，幻燈片也看了好多，大同小異，入了門之後初級的差不多都能看懂。網上的資料有好多，我就不在這畫蛇添足了，大家想學的一搜就能搜到好多的。

對于反演，我也是剛剛入門，可能都達不到入門的水準，這篇部落格我還會再修改的，這隻是1.0版本，好了，羅嗦了一大堆，上代碼。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int mu[60000];
int prime[600000];
int vis[600000];
int cnt;
void Init()//u(x)
{
    memset(vis,0,sizeof(vis));
    mu[1] = 1;
    cnt = 0;
    for(int i=2; i<=50000; i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0; j<cnt&&i*prime[j]<=50000; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}
int k;
long long fax(int n,int m)
{
    n/=k;
    m/=k;
    long long sum=0;
    int p=min(n,m);
    for(int i=1;i<=p;i++)
    {
        sum+=mu[i]*(n/i)*(m/i);
    }
    return sum;
}
int main()
{
    int t;
    Init();
    int a,b,c,d;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        long long sum=0;
        sum+=fax(b,d);
        sum-=fax(a-1,d);
        sum-=fax(b,c-1);
        sum+=fax(a-1,c-1);//容斥原理
        cout<<sum<<endl;
    }
    return 0;
}
 
           

大神們路過時請留下你寶貴的修改意見，感激不盡！