刚开始看题，想了一会想到了一种容斥的做法。复杂度O( n(3/2) )但是因为题目上说有3000组测试数据，然后吓尿。完全不敢写。 然后想别的方法。
唉，最近精神有点问题，昨天从打完bc开始想到1点多，没想到什么好的方法，然后躺床上睡不着，迷迷糊糊又好像挺清醒的，大概想到了用莫比乌斯反演的一种解法，初略的证明了一下发现应该是对的，然后才逐渐有困意，大概也快天亮了。。。 这种事发生了好几次了。上次在证明莫比乌斯反演的时候也是想到快5点才想出来。 感觉整个人都不好了。。
题目： 求在区间[1,b]和[1,d]中各选一个数，使得这两个数的gcd为k，问有多少种选法。
稍微推理下问题可以变为：在区间[1,b/k]和[1,d/k]中选两个gcd为1的数。
设b1=b/k,d1=d/k,假设b1<d1 (b1>b1时swap一下就好了)
F(x) 表示从区间[1,b1/x]和区间[1,d1/x]中任意选两个数，有多少选数的方法，其实就是(b1/x)*(d1/x)了。
f(y) 表示从区间[1,b1]和区间[1,d1]中选两个数，使得这两个数的gcd为y的所有种选法。
那么就可以得到:
F(1)=f(1)+f(2)+...+f(b1)
F(2)=f(2)+f(4)+...+f( (b1/2)*2 )
F(3)=f(3)+f(6)+...+f( (b1/3)*3 )
...
F(b1)=f(b1)
然后莫比乌斯函数miu(n)为最经典的莫比乌斯函数。
if n== 1
miu(n)=1
else
if n只由不重复的素数构成
{
if(不重复的素数个数为偶数) miu(n)=1;
else miu(n)=-1;
}
else
miu(n)=0
//其实这个只要懂了莫比乌斯反演的原理，还是很好理解的。
有了整个主题思维后，
f(1)=miu(1)*F(1)+miu(2)*F(2)+...+miu(b1)*F(b1)
因为F(x)是显而易见的，我当时一直在以往的因子和里面纠结着，以为莫比乌斯只能应用于求因子的积性函数中。其实莫比乌斯的应用远不如此。要用莫比乌斯的关键是如何找到一个很容易得到F(X)。
得到了f(1)之后还需要去重复，这个就好弄多了。
得到1-b1中所有数的欧拉函数之和sum，f(1)-sum+1即为最后的答案。
详细的见代码：
//
// main.cpp
// hdu1695
//
// Created by 陈加寿 on 15/12/13.
// Copyright (c) 2015年 陈加寿. All rights reserved.
// #include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
#define N 100100 int miu[N];
long long sum[N]; int phi[N];
void getphis(int maxn)
{
phi[]=;
phi[]=;
for(int i=;i<=maxn;i++) phi[i]=i;
for(int i=;i<=maxn;i+=) phi[i]/=;
for(int i=;i<=maxn;i+=)
{
if(phi[i]==i)//为素数
{
for(int j=i;j<=maxn;j+=i)
{
phi[j]=phi[j]-phi[j]/i; }
}
}
} int main() {
miu[]=;
for(int i=;i<N;i++)
{
int ti=i;
int tcnt=;
for(int j=;j*j<=ti;j++)
{
if(ti%j==)
{
ti/=j;
tcnt++;
if(ti%j==)
{
tcnt=-;
miu[ i ]=;
break;
}
}
}
if(tcnt!=-)
{
if(ti>)
{
tcnt++;
}
miu[i] = tcnt%==?:-;
}
}
getphis(N-);
sum[]=;
for(int i=;i<N;i++)
sum[i] += sum[i-]+phi[i]; int tt=;
int T;
cin>>T;
while(T--)
{
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("Case %d: ",tt++);
if(k==)
{
//这个是什么鬼。
printf("0\n");
continue;
} b/=k;
d/=k; if(b== || d==)
{
printf("0\n");
continue;
}
if(b>d) swap(b,d);
long long ans=;
for(int i=;i<=b;i++)
{
ans += miu[i]*( (long long)(b/i)*(d/i) );
}
ans -= sum[b];
cout<<ans+<<endl;
}
return ;
}
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8094 Accepted Submission(s): 3017
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
1 3 1 5 1
1 11014 1 14409 9
Case 2: 736427
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).