[HAOI2011] Problem b

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
基本莫比乌斯反演套路。
原式等价于
(sum _{i=1} ^{i<=[n/k]} sum _{j=1} ^{j<=[m/k]} [gcd(i,j)==1])
等价于 (sum _{d=1} ^{d<=n} mu (d) sum _{i=1} ^{i<=[n/(d*k)]} sum _{j=1} ^{j<=[m/(d*k)]} 1)
数论分块做一下就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=50005;
int prime[N],cnt,miu[N],a,b,c,d,e,sum[N],k;
bool vis[N];
void get_miu() {
    miu[1]=1;
    for(int i=2;i<=N-5;i++) {
        if(!vis[i]) prime[++cnt]=i,miu[i]=-1;
        for(int j=1;prime[j]*i<=N-5&&j<=cnt;j++) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
            miu[i*prime[j]]=-miu[i];
        }
    }
    for(int i=1;i<=N-5;i++) sum[i]=sum[i-1]+miu[i];
}
int T;
int get_ans(int x,int y) {
    int ans=0;
    if(x>y) swap(x,y);
    for(int i=1,nxti;i<=x;i=nxti+1) {
        nxti=min(x/(x/i),y/(y/i));
        ans+=(x/(i*k))*(y/(i*k))*(sum[nxti]-sum[i-1]);
    }
    return ans;
}
int main() {
    get_miu();
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%d
",get_ans(b,d)-get_ans(a-1,d)-get_ans(b,c-1)+get_ans(a-1,c-1));
    }
}