这道题和hdu1965思路基本类似， http://blog.csdn.net/abc13068938939/article/details/52198163 mobius反演得出的结果是(过程在上面的博文中有介绍) 1< =i< =m和1< =j< =n中gcd（i,j）=k的个数 令m~=m/k, n~=n/k。且不妨设m < = n。
f(1)=Sigma(d=1 : m) u(d)* ((m~)/d) *((n~)/d)。
m/=k,n/=k; if(m>n) swap(n,m); LL res=0ll; for(int i=1;i<=m;i++) res+=u(i)*(m/i)*(n/i);然后a< =i< =b和c< =j< =d中gcd（i,j）=k的个数= solve(b/k,d/k)-solve(b/k,(c-1)/k)-solve((a-1)/k,d/k)+solve((a-1)/k,(c-1)/k)。 其中solve(n,m)表示1< =i< =m和1< =j< =n中gcd（i,j）=1的个数。 但是这是会超时的， 事实上m/i它在一小块内是不会变的，比如 m=100 i=26:33，m/i均等于3，也就是这一部分可以合着计算。 分块不熟可以看这道题bzoj1257(余数之和)
#include <iostream> #include <stdio.h> #include <algorithm> #include <stdlib.h> #include <stack> #include <vector> #include <string.h> #include <queue> #define msc(X) memset(X,-1,sizeof(X)) #define ms(X) memset(X,0,sizeof(X)) typedef long long LL; using namespace std; const int MAXN=50005; int sum[MAXN+10],mu[MAXN+10]; void getMobius(void) { for(int i=1;i<=MAXN;i++) { int target=(i==1?1:0); int delta=target-mu[i]; mu[i]=delta; for(int j=i+i;j<=MAXN;j+=i) mu[j]+=delta; } } LL solve(int x,int y) { LL res=0ll; for(int i=1,r;i<=x&&i<=y;i=r+1) { int dx=x/i,dy=y/i; r=min(x/dx,y/dy); res+=(LL)(sum[r]-sum[i-1])*dx*dy; } return res; } int main(int argc, char const *argv[]) { int n; cin>>n; ms(mu); getMobius(); sum[0]=0; for(int i=1;i<=MAXN;i++) sum[i]=sum[i-1]+mu[i]; while(n--){ int a,b,c,d,k; scanf("%d %d %d %d %d",&a,&b,&c,&d,&k); a=(a+k-1)/k,c=(c+k-1)/k;//向上取整 b/=k,d/=k;//向下取整 LL ans=solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1); printf("%lld\n",ans ); } return 0; }