刚开始看题，想了一会想到了一种容斥的做法。复杂度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[1]=1; phi[2]=1; for(int i=2;i<=maxn;i++) phi[i]=i; for(int i=2;i<=maxn;i+=2) phi[i]/=2; for(int i=3;i<=maxn;i+=2) { if(phi[i]==i)//为素数 { for(int j=i;j<=maxn;j+=i) { phi[j]=phi[j]-phi[j]/i; } } } } int main() { miu[1]=1; for(int i=2;i<N;i++) { int ti=i; int tcnt=0; for(int j=2;j*j<=ti;j++) { if(ti%j==0) { ti/=j; tcnt++; if(ti%j==0) { tcnt=-1; miu[ i ]=0; break; } } } if(tcnt!=-1) { if(ti>1) { tcnt++; } miu[i] = tcnt%2==0?1:-1; } } getphis(N-1); sum[0]=0; for(int i=1;i<N;i++) sum[i] += sum[i-1]+phi[i]; int tt=1; 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==0) { //这个是什么鬼。 printf("0 "); continue; } b/=k; d/=k; if(b==0 || d==0) { printf("0 "); continue; } if(b>d) swap(b,d); long long ans=0; for(int i=1;i<=b;i++) { ans += miu[i]*( (long long)(b/i)*(d/i) ); } ans -= sum[b]; cout<<ans+1<<endl; } return 0; }
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.