参考了：HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET
题意：求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。
思路：问题可以转化：在b和d分别除以k之后的区间里，只需要求gcd(x, y) = 1就可以了。
题目还要求1-3 和 3-1 这种情况算成一种，因此需要限制x<y。
只需要枚举x，然后确定另一个区间里面有多少个y就可以了。因此问题转化成为区间（1， d）里面与x互素的数的个数
①(1...b)与(1...b)中有多少对数互质
②(1...b)与(b+1...d)中有多少对数互质
问题1就是欧拉函数的应用，下面的代码没有用这个，直接和问题2一起解决，牺牲了一些速度。
问题2从反面考虑，对于(b+1...d)中的每一个y，要想知道(1...b)中有多少数与它互质，
我们只需要知道多少个数与它不互质即可。而两个数不互质就意味着它们有公因子。
对于每一个y的因子f，都能确定地知道(1...b)中有多少个数含有因子f，用容斥原理算一下，
就能知道(1...b)中有多少个数与y互质了。枚举y即可解决问题。
如果w是x的因子，则（1，d）中是w倍数的数共有d/w个。
容斥原理：所有不与x互素的数的个数= 1个因子倍数的个数 - 2个因子乘积的倍数的个数 + 3个……-……
以下转自AC神：http://hi.baidu.com/aekdycoin/item/4c8d4089e5011759840fabad
关于区间gcd统计的小问题
1.求[1,n]内和n的gcd=k的个数
转换为求区间[1,n/k]内和n/k互质的数的个数
2.求[1,m]内和n互质的数的个数
容斥原理
3.求[1,m]内和n的gcd=k的个数
转化模型,同上
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
const int N=100005;
vector<int> data[N];
bool tag[N];
void Prime ()
{//预处理素数,同时记录每一个数的素因子
int i,j;
memset(tag,false,sizeof(tag));
for (i=0;i<N;i++)
data[i].clear();
for (j=2;j<N;j+=2)
data[j].push_back(2);
for (i=3; i<N; i+=2) if (tag[i]==false)
for (j=i;j<N;j+=i)
{
tag[j] = true;
data[j].push_back(i);
}
}
int Deal (int u,int state,int id)
{
int cnt=0,v=1; //v 因子
for (int i=0; i<data[id].size(); i++)
if ((1<<i) & state)
{
cnt++;
v *= data[id][i];
}
int all=u/v;
if (cnt%2==0)
return -all;
else
return all;
}
int main ()
{
Prime();
int T;
scanf("%d", &T);
for (int Cas=1;Cas<=T;Cas++)
{
int b,d,k;
scanf("%*d%d%*d%d%d",&b,&d,&k);
if (k==0)
{
printf("Case %d: 0\n",Cas);
continue;
}
b/=k;
d/=k;
if (b>d)
swap(b,d);
__int64 ans=0;
for (int i=1;i<=d;i++)
{//枚举y,求1~d中与x互素的个数
int x=min(i,b);
ans+=x; //假设全都互素,然后减掉不互素的
for (int j=1;j<(1<<data[i].size());j++)
ans -= Deal(x,j,i);
}
printf("Case %d: %I64d\n",Cas,ans);
}
return 0;
}