莫比乌斯反演bzoj-2301

发布于 2018-06-02  195 次阅读


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

思路:莫比乌斯反演’

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=5e4+20;
int tot;
int a,b,c,d,k;
int sum[maxn],mu[maxn],pri[maxn];
bool mark[maxn];
void getmu()
{
    mu[1]=1;
    for(int i=2; i<maxn; i++)
    {
        if(!mark[i])
        {
            mu[i]=-1;
            pri[++tot]=i;
        }
        for(int j=1; j<=tot&&i*pri[j]<maxn; j++)
        {
            mark[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                mu[i*pri[j]]=0;
                break;
            }
            else mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1; i<maxn; i++)
        sum[i]=sum[i-1]+mu[i];
}
int cal(int n,int m)
{
    if(n>m)swap(n,m);
    int ans=0,pos;
    for(int i=1; i<=n; i=pos+1)
    {
        pos=min(n/(n/i),m/(m/i));
        ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main()
{
    getmu();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        a--;c--;
        a/=k;b/=k;c/=k;d/=k;
        int ans=cal(a,c)+cal(b,d)-cal(a,d)-cal(b,c);
        printf("%d\n",ans);
    }
    return 0;
}
/*
2 3 4 5
1 2 3 4 5
2 2  2 4  4 2
3 3
4 4
5 5
*/

补充:递推求逆元:

ni[1]=1;
    ll p=mod;
    for(int i=2;i<=maxn;i++)
        ni[i]=(p-p/i)*ni[p%i]%p;

Comments


愿我如星君如月,夜夜流光相皎洁。