组合 数论 莫比乌斯反演 hdu1695

题解：https://blog.csdn.net/lixuepeng_001/article/details/50577932

题意：给定范围1-b和1-d求（i，j）=k的数对的数量

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstring>

using namespace std;

const int MAXN = ;

bool check[MAXN+];

long long mu[MAXN+];

long long a,b,c,d,k;

const int N = 1e6 + ;

long long mob[N], vis[N], prime[N];

int tot;//用来记录prime的个数

void Mobius(int n){   //求得莫比乌斯函数值

    memset(prime,,sizeof(prime));

    memset(mob,,sizeof(mob));

    memset(vis,,sizeof(vis));

    tot = , mob[] = ;

    for(int i = ; i <=n; i ++){

        if(!vis[i]){

            prime[tot++] = i;

            mob[i] = -;

        }

        for(int j = ; j < tot && i * prime[j] <=n ; j ++){

            vis[i * prime[j]] = ;

            if(i % prime[j]) mob[i * prime[j]] = -mob[i];

            else{

                mob[i * prime[j]] = ;

                break;

            }

        }

    }

}

int main()

{

    int T;

    Mobius(N);

    cin>>T;

    int Case=;

    while(T--)

    {

        cin>>a>>b>>c>>d>>k;

        cout<<"Case "<<++Case<<": ";

        if(k==){

            cout<<""<<endl;

            continue;

        }

        b=b/k;

        d=d/k;

        long long ans1=;

        long long ans=;

        for(long long i=;i<=min(b,d);i++)

        {

            ans+=mob[i]*(b/i)*(d/i);

            ans1+=mob[i]*((min(b,d)/i)*(min(b,d)/i));

        }

        printf("%lld\n",ans-(ans1/));

    }

}