ACWING2702.problem b

原题链接

描述

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

思路

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
int primes[N],cnt,mu[N];
bool st[N];
int sum[N];
void init(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!st[i]) primes[cnt++]=i,mu[i]=-1;
        for(int j=0;primes[j]*i<N;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
            mu[primes[j]*i]=-mu[i];
        }
    }
    for(int i=1;i<N;i++) sum[i]=sum[i-1]+mu[i];
}
int g(int k,int x){
    return k/(k/x);
}
ll f(int a,int b,int k){
    a=a/k,b=b/k;
    ll res=0;
    int n=min(a,b);
    for(int l=1,r;l<=n;l=r+1){
        r=min(n,min(g(a,l),g(b,l)));
        res+=(ll)(sum[r]-sum[l-1])*(a/l)*(b/l);
    }
    return res;
}

int main(){
    init();
    int t; scanf("%d",&t);
    while(t--){
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%lld\n",f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k));
    }
    return 0;
}