题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，，gcd(x,y)函数为x和y的最大公约数
思路：在hdu1695的基础上加上容斥，即:ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k),详见代码：
/********************************************************* file name: bzoj2301.cpp author : kereo create time: 2015年02月17日 星期二 10时46分33秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=100+50;const int MAXN=50000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int primecnt;int vis[MAXN],mu[MAXN],prime[MAXN],sum[MAXN];void Mobius(){primecnt=0;memset(vis,0,sizeof(vis));mu[1]=1;for(int i=2;i<MAXN;i++){if(!vis[i]){prime[primecnt++]=i;mu[i]=-1;}for(int j=0;j<primecnt && i*prime[j]<MAXN;j++){vis[i*prime[j]]=1;if(i%prime[j])mu[i*prime[j]]=-mu[i];else{mu[i*prime[j]]=0;break;}}}}ll solve(int l,int r){ll ans=0;if(l>r)swap(l,r);int last;for(int i=1;i<=l;i=last+1){last=min(l/(l/i),r/(r/i));ans+=(ll)(sum[last]-sum[i-1])*(l/i)*(r/i);}return ans;}int main(){Mobius();sum[0]=0;for(int i=1;i<MAXN;i++)sum[i]=sum[i-1]+mu[i];int T;scanf("%d",&T);while(T–){int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);ll ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve((c-1)/k,b/k)+solve((a-1)/k,(c-1)/k);printf("%lld\n",ans);}return 0;}
或者在河边放下一盏写着心愿的河灯，祝愿一切安好。
