http://www.lydsy.com/JudgeOnline/problem.php?id=1101
题意很简单
意思就是给你下a,b,d;
问x<=a&&y<=b&&gcd(x,y)==k
典型的mobius函数的模板题
但是朴素的求法会超时
所以可以利用一种除数分块的思想
在某种距离之内是不会改变的
AC代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50000; int miu[N+10],v[N+10],P[N+10]; inline void read(int &x){char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok) x=-x;} int main(){ for(int i=1;i<=N;i++) miu[i]=1,v[i]=0; for(int i=2;i<=N;i++){ if(v[i]) continue; miu[i] = -1; for(int j=2*i;j<=N;j+=i){ v[j]=1; if((j/i)%i==0) miu[j]=0; else miu[j]*=-1; } } for(int i=1;i<=N;++i) P[i]=P[i-1]+miu[i]; int T; read(T); while(T--){ int a,b,k; read(a); read(b); read(k); a=a/k; b=b/k; int ans=0; int c; for(int i=1;i<=min(a,b);i=c+1){ c=min(a/(a/i),b/(b/i)); ans+=(P[c]-P[i-1])*(a/i)*(b/i); } printf("%d\n",ans); } }