BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演

2022-11-21 21:10:09

2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 1007 Solved: 415
[Submit][Status]

Description

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2 5 1 5 1

1 5 1 5 2

Sample Output

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

mobius反演，与“能量采集”不同的是，这道题如果不加一点优化的话，是一定会TLE的。然后考虑优化：

　　ans+=segma(mu[i]*(a/i)*(b/i))

由于对于一个给定的区间[l,r]， a/l=a/r b/l=b/r，可以对对这个区间统一处理。

　　ans+=segma((sum[r]-sum[l-1])*(a/l)*(n/l))

所以令l=i，这里要记一下

　　a/(a/i)==r+1

所以剩下的就可以随便搞一下了。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

#ifdef unix

#define LL "%lld"

#else

#define LL "%I64d"

#endif

typedef long long qword;

#define MAXN 100000

int prime[MAXN/];

bool pflag[MAXN];

int topp=-;

int mu[MAXN];

int sum[MAXN];

void init()

{

        int i,j;

        mu[]=;

        for (i=;i<MAXN;i++)

        {

                if (!pflag[i])

                {

                        prime[++topp]=i;

                        mu[i]=-;

                }

                for (j=;j<=topp&&prime[j]*i<MAXN;j++)

                {

                        pflag[i*prime[j]]=true;

                        mu[i*prime[j]]=-mu[i];

                        if (i%prime[j]==)

                        {

                                mu[i*prime[j]]=;

                        }

                }

        }

}

qword solve(int a,int b)

{

        int l=min(a,b);

        int i,j;

        int ls,lt;

        qword ret=;

        for (i=,ls=;i<=l;i=ls+)

        {

                ls=min((a/(a/i)),(b/(b/i)));

                ret+=(qword) (sum[ls]-sum[i-])*(a/i)*(b/i);

        }

        return ret;

}

int main()

{

        int nn;

        freopen("input.txt","r",stdin);

        init();

        scanf("%d",&nn);

        int a,b,c,d,n;

        qword ans;

        int i,j;

        for (i=;i<MAXN;i++)sum[i]=sum[i-]+mu[i];

/*        for (i=1;i<10;i++)

        {

                for (j=0;j<10;j++)

                {

                        cout<<i<<" "<<j<<" "<<solve(i,j)<<endl;

                }

        }

*/

    //    cout<<solve(2,3);

    //    return 0;

        while (nn--)

        {

                scanf("%d%d%d%d%d",&a,&b,&c,&d,&n);

                ans=solve((a-)/n,(c-)/n)-solve((a-)/n,d/n)-solve(b/n,(c-)/n)+solve(b/n,d/n);

                printf(LL "\n",ans);

        }

}

码农公寓