hdu1695-GCD-莫比乌斯反演

题目链接

题意：给出a,b,c,d,k, 求满足a <= x <= b && c <= y <= d && gcd(x,y)=k 的数对(x,y)的对数。

思路：强行抄一个莫比乌斯的题解，给子留个板子……虽然感觉到时候就算遇到也不会用……莫比乌斯难的不是实现（好吧，数论的实现都不会太难）而是构造出满足条件又能计算的F(n)函数
推荐这两个博客：莫比乌斯反演学习资料
本题简便解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long N =100005;
int vis[100005];
int mu[100005];
int prime[100005];
int cnt;
void Init()  
{  
    memset(vis,0,sizeof(vis));  
    mu[1] = 1;  
    cnt = 0;  
    for(int i=2; i<N; i++)  
    {  
        if(!vis[i])  
        {  
            prime[cnt++] = i;  
            mu[i] = -1;  
        }  
        for(int j=0; j<cnt&&i*prime[j]<N; j++)  
        {  
            vis[i*prime[j]] = 1;  
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];  
            else  
            {  
                mu[i*prime[j]] = 0;  
                break;  
            }  
        }  
    }  
}  
int main()
{ 
  int i,j,k,m,n;
  int t;
  scanf("%d",&t);
  Init();
  int kase=0;
  while(t--)
  {kase++;
   printf("Case %d: ",kase);
  
  	int a,b,c,d,k;
  	scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
	   if(k==0)
   {
   	printf("0\n");
   	continue;
   }
  	if(b>d)swap(b,d);
  	b=b/k;
  	d=d/k;
  	long long ans1=0;
	for(int i=1;i<=b;i++)
  	{
  	  	ans1+=(long long )mu[i]*(b/i)*(d/i);
	  }
	long long ans2=0;  
	for(int i=1;i<=b;i++)
	{
		ans2+=(long long )mu[i]*(b/i)*(b/i);
	  }
	ans1=ans1-ans2/2;
	printf("%lld\n",ans1);    
  }
  return 0;
 }

一些后话：还有一周就要去合肥参加ccpc了……感觉现在还是什么都不会……dp全都靠算命，数学全靠抄题解，图论一窍不通，数据结构一跑就炸，水题一交就挂……只能靠两个队友了。诶，就当公费去合肥旅个游吧。不知道为什么，最近沉迷余秋雨的散文，总感觉他的散文读起来太腻，有些作，但是却又想看，连上今天一个多星期就看完了一本。或许是因为尽管他的文风有些浮夸，但是思想确实能让人感觉新颖吧。