【bzoj1101】Zap

题目大意

对于给出的n个询问，每次求有多少个数对$(x,y)$

满足$1\leqslant x\leqslant a,1\leqslant y\leqslant b$,且$gcd(x,y)=c$

数据范围

$1\leqslant n\leqslant 50000,1\leqslant c\leqslant a,b\leqslant 50000$

题解

原题是求$\sum^{a}_{i=1}\sum^{b}_{j=1}1{(gcd(i,j)=c)}$

设$A=\left\lfloor\frac{a}{c}\right\rfloor,B=\left\lfloor\frac{b}{c}\right\rfloor$

则原式=$\sum^{A}_{i=1}\sum^{B}_{j=1}1{(gcd(i,j)=1)}$

根据莫比乌斯函数的性质,$\sum_{c|n}\mu(c)=1\{n=1\}0\{n\neq 1\}$

因此原式=$\sum^{A}_{i=1}\sum^{B}_{j=1}\sum_{c|gcd(i,j)}\mu(c)$

容易发现,$\mu(c)$加了的次数是$\sum^{A}_{i=1}\sum^{B}_{j=1}1{(c|i,c|j)}$

所以原式可以再次化简为$\sum\mu(c)\left\lfloor\frac{A}{c}\right\rfloor\left\lfloor\frac{B}{c}\right\rfloor$

由于$\left\lfloor\frac{A}{c}\right\rfloor$是$\sqrt{A}$数量级的，所以分段处理

【bzoj2301】Problem b

题目大意

对于给出的$n$个询问，每次求有多少个数对$(x,y)$

满足$a\leqslant x\leqslant b,c\leqslant y\leqslant d$,且$gcd(x,y)=k$

数据范围

$1\leqslant n\leqslant 50000,1\leqslant a\leqslant b\leqslant 50000,1\leqslant c\leqslant d\leqslant 50000,1\leqslant k\leqslant 50000$

题解

这道题其实和上题一样，只是要利用容斥原理处理信息

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x7fffffff
using namespace std;

int sum[50050],mu[50050],prime[50050],flag[50050];
int tot,ans,a,b,c,d,k,t;

inline void getmu(){
    mu[1]=1;
    For(i,2,50000){
        if (!flag[i]) {prime[++tot]=i;mu[i]=-1;}
        For(j,1,tot){
            if (i*prime[j]>50000) break;
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) {mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
}
inline int count(int x,int y){
    if (x>y) swap(x,y);
    int result=0,pos;
    for(int i=1;i<=x;i=pos+1){
        pos=min(x/(x/i),y/(y/i));
        result+=(sum[pos]-sum[i-1])*(x/i)*(y/i);
    }
    return result;
}
int main(){
    getmu();
    For(i,1,50000) sum[i]=sum[i-1]+mu[i];
    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;
        ans=count(a,c)+count(b,d)-count(a,d)-count(b,c);
        printf("%d\n",ans);
    }
    return 0;
}