首页 > 代码库 > BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演

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

2024-07-08 12:13:45   232人阅读

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

2 5 1 5 1

1 5 1 5 2



Sample Output


14

3



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"#endiftypedef long long qword;#define MAXN 100000int prime[MAXN/3];bool pflag[MAXN];int topp=-1;int mu[MAXN];int sum[MAXN];void init(){        int i,j;        mu[1]=1;        for (i=2;i<MAXN;i++)        {                if (!pflag[i])                {                        prime[++topp]=i;                        mu[i]=-1;                }                for (j=0;j<=topp&&prime[j]*i<MAXN;j++)                {                        pflag[i*prime[j]]=true;                        mu[i*prime[j]]=-mu[i];                        if (i%prime[j]==0)                        {                                mu[i*prime[j]]=0;                        }                }        }}qword solve(int a,int b){        int l=min(a,b);        int i,j;        int ls,lt;        qword ret=0;        for (i=1,ls=0;i<=l;i=ls+1)        {                ls=min((a/(a/i)),(b/(b/i)));                ret+=(qword) (sum[ls]-sum[i-1])*(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=0;i<MAXN;i++)sum[i]=sum[i-1]+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-1)/n,(c-1)/n)-solve((a-1)/n,d/n)-solve(b/n,(c-1)/n)+solve(b/n,d/n);                printf(LL "\n",ans);        }}

 


联系
我们