Problem b

题目描述

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

输入

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

输出

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

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

来源

HAOI2011

solution

令 $f[i][j]=\sum_{i-1}^{n} \sum_{j-1}^{m} [gcd(i,j)==k]$

首先用类似前缀和的方法

题目求f(b,d)-f(a-1,d)-f(c-1,b)+f(a-1,c-1)

这样子就好求了不少

按照套路反演

$\sum_{d} \mu(d) \sum_{i-1}^{n/kd} \sum_{j-1}^{m/kd}$

那么我们算同一个询问的效率就是O（n）的了

这时发现询问数很多

注意到在一定范围内n/kd，m/kd是相同的,可以一起算

范围是多少呢

假设当前为i,nex=n/(n/i)

很好理解，我要找的是连续最长的一段，都等于n/i

n/(n/i)就是最大的那一个，也就是右端

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 50008

#define ll long long

using namespace std;

int T,n,a,b,c,d,k,mu[maxn];

int pri[maxn],flag[maxn],tot;

void init(){

    n=50000;

    mu[1]=1;

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

        if(!flag[i])mu[i]=-1,pri[++tot]=i;

        for(int j=1;j<=tot&&pri[j]<=n/i;j++){

            flag[i*pri[j]]=1;mu[i*pri[j]]=-mu[i];

            if(i%pri[j]==0){

                mu[pri[j]*i]=0;break;

            }

        }

        mu[i]+=mu[i-1];

    }

}

ll C(int x,int y){

    ll ans=0;

    if(x<y)swap(x,y);

    for(int i=1;i<=y;){

        int l=i,r=min(x/(x/i),y/(y/i));

        ans=ans+(1LL)*(mu[r]-mu[l-1])*(x/i)*(y/i);

        i=r+1;

    }

    return ans;

}

void work(){

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

    ll tmp=C(b/k,d/k)-C(d/k,(a-1)/k)-C(b/k,(c-1)/k)+C((a-1)/k,(c-1)/k);

    printf("%lld\n",tmp);

}

int main(){

    init();

    cin>>T;while(T--)work();

    return 0;

}

巴特西

Problem b

Problem b

题目描述

输入

输出

来源

最新文章

热门文章