Description
给定 $N,M$,求 $1 leq x leq N$,$1 leq y leq M$ 且 $gcd(x,y)$ 为质数的$(x,y)$ 有多少对。
Solution
题目要求$sum_{i=1}^{n}sum_{j=1}^{m}[gcd(x,y) in prime]$
设
$$f(d)=sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=d]$$
$$F(x)=sum_{x|d}f(d)=lfloorfrac{n}{x} floorlfloorfrac{m}{x} floor$$
则有莫比乌斯反演
$$f(n)=sum_{n|d}mu(lfloorfrac{d}{n} floor)F(d)$$
化简原式:
egin{align}
& sum_{pin prime}sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=p]\
= & sum_{pin prime}f(p)\
= & sum_{pin prime}sum_{p|d}mu(frac{d}{p})F(d)\
= & sum_{pin prime}sum_{d=1}^{min(lfloorfrac{n}{p}
floor,lfloorfrac{m}{p}
floor)}mu(d)F(dp)\
= & sum_{pin prime}sum_{d=1}^{min(lfloorfrac{n}{p}
floor,lfloorfrac{m}{p}
floor)}mu(d)lfloorfrac{n}{dp}
floorlfloorfrac{m}{dp}
floor\
= & sum_{T=1}^{min(n,m)}sum_{t|T,tin prime}mu(frac{T}{t})lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor\
= & sum_{T=1}^{min(n,m)}lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor(sum_{t|T}mu(frac{T}{t}))
end{align}
数论分块即可
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int prime[10000005],mu[10000005],n,m,tot; long long T,ans,sum[10000005]; bool vst[10000005]; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return f*w; } inline void write(long long x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0'); } int main() { //freopen("P2257.in","r",stdin); //freopen("ans.txt","w",stdout); mu[1]=1; for(int i=2;i<=10000000;i++) { if(!vst[i]) { prime[++tot]=i; mu[i]=-1; } for(int j=1;j<=tot&&i*prime[j]<=10000000;j++) { vst[i*prime[j]]=true; if(!(i%prime[j])) { break; } else { mu[i*prime[j]]=-mu[i]; } } } for(int i=1;i<=5000000;i++) { for(int j=1;j<=tot&&i*prime[j]<=10000000;j++) { sum[i*prime[j]]+=mu[i]; } } for(int i=1;i<=10000000;i++) { sum[i]+=sum[i-1]; } T=read(); for(;T;T--) { ans=0; n=read(); m=read(); if(n>m) { swap(n,m); } for(int i=1;i<=n;) { int j=min(n/(n/i),m/(m/i)); ans+=1ll*(n/i)*(m/i)*(sum[j]-sum[i-1]); i=j+1; } write(ans); putchar(10); } return 0; }