思路
其实就是P3455套了个简单的容斥
把问题转化成f(n,m,k)-f(a-1,m,k)-f(n,b-1,k)+f(a-1,b-1,k)就可以了和p3455几乎一样的代码
#include#include #include using namespace std;int T,n,m,mu[51000],iprime[51000],isprime[51000],summu[51000],cnt,k;void prime(int n){ isprime[1]=true; mu[1]=1; for(int i=2;i<=n;i++){ if(!isprime[i]) iprime[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&iprime[j]*i<=n;j++){ isprime[iprime[j]*i]=true; mu[iprime[j]*i]=-mu[i]; if(i%iprime[j]==0){ mu[iprime[j]*i]=0; break; } } } for(int i=1;i<=n;i++) summu[i]=summu[i-1]+mu[i];}long long f(int k){ long long ans=0; for(int l=1,r;l<=min(n,m);l=r+1){ r=min((n/(n/(l))),(m/(m/(l)))); ans+=1LL*(summu[r]-summu[l-1])*(n/(l*k))*(m/(l*k)); } return ans;}int main(){ prime(50100); scanf("%d",&T); while(T--){ scanf("%d %d %d",&n,&m,&k); if(n