定理：\(F(n)\)和\(f(n)\)是定义在非负整数上的两个函数，并存在\(F(n)=\sum_{d|n}^{}f(d)\)，那么我们得到结论 \[f(n)=\sum_{d|n}^{}\mu(d)F(\frac{n}{d})\] 上文中的\(\mu(d)\)函数，我们用以下方式来定义 （1）如果\(d=1\)，那么\(\mu(d)=1\) （2）如果\(d=p_{1}p_{2}\cdots p_k\)，且\(p_i\)为互不相同的素数，那么\(\mu(d)=(-1)^k\) （3）其他情况\(\mu(d)=0\) 以上是对莫比乌斯反演的第一种表述，实际上，我们还常常用到第二种表示 \[F(n)=\sum_{n|d}^{}f(d) \Rightarrow f(n)=\sum_{n|d}^{}\mu(\frac{d}{n})F(d)\] 这个表述有一个奇怪的问题就是\(n|d\)这里，要找到所有的能整除\(n\)的\(d\)，这样的话\(d\)的个数显然就是无穷多，但是我们在实际的题目中，通常当\(d\)的值过大时，\(F(d)\)的值就为\(0\)， 接下来的题目中会有例子。 就本质上而言，我们对\(f(n)\)的计算，实际上就是通过\(F(n)\)进行容斥，最后算出\(f(n)\)，一般来说题目的\(F(n)\)都比较好计算。 对于\(\mu(d)\)函数，有如下性质 （1）对于任意正整数\(n\)有 \[\sum_{d|n}^{}\mu(d)=\begin{cases}1& \text{n=1}\\ 0& \text{n>1}\end{cases}\] （2）对于任意正整数\(n\)有 \[\sum_{d|n}^{}\frac{\mu(d)}{d}=\frac{\phi(n)}{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
| 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;
}
}
}
}
|
学习这个东西的动机呢...就是有个求计数论大神，连续两场出了这个东西，第一场的范围还比较小，可以用容斥一战，第二场就比较感人...其实就是一个莫比乌斯裸题
给定一个\(n\)和一个\(m\)，找到\(1\le i\le n\)和\(1\le j\le m\)使\(gcd(i,j)=1\)的总共对数
我们只需要简单设计一下\(f(n)\)和\(F(n)\)就行啦 \(f(d)\)为\(gcd(x,y)=d\)且\(1\le x\le n\)，\(1\le y\le m\)的\((x,y)\)对数 \(F(d)\)为\(d|gcd(x,y)\)且\(1\le x\le n\)，\(1\le y\le m\)的\((x,y)\)对数 这两个函数显然符合表述\[F(n)=\sum_{n|d}^{}f(d) \Rightarrow f(n)=\sum_{n|d}^{}\mu(\frac{d}{n})F(d)\] 而且对于\(d\)特别大的情况，显然\(f(d)\)和\(F(d)\)都为\(0\)。 观察\(F(d)\)，显然\[F(d)=\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\] 题目要求的就是\(f(1)\)的值，那么只需要暴力求就好了...是不是特别的裸orz
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
| #include<bits/stdc++.h>
#define maxn 10000000
#define mod 100000007
using namespace std;
bool vis[10000010]={};
int prime[10000010]={};
int mu[10000010]={};
int cnt=0;
void Init()
{
mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
}
void work()
{
long long n,m;
scanf("%lld%lld",&n,&m);
long long ans=0;
for(int i=1;i<=n;i++)
{
long long a,b;
a=n/i;
b=m/i;
ans+=mu[i]*a*b;
ans=(ans+mod)%mod;
}
printf("%lld\n",ans);
}
int main()
{
Init();
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}
|
事实上最后暴力求\(f(1)\)这里还可以稍稍优化一下，从\(O(n)\)优化成\(O(\sqrt{n})\)，下一题就需要这种优化... http://www.lydsy.com/JudgeOnline/problem.php?id=1101
给定一个\(n\)和一个\(m\)，找到\(1\le i\le n\)和\(1\le j\le m\)使\(gcd(i,j)=d\)的总共对数，询问的次数最多可以是\(50000\)
像上道题一样裸着搞一定会T掉的！ 我们观察一下，发现\[F(d)=\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\] 这个式子中的\[\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\]部分，并不会因为\(i\)的不同而连续变化，这个值是跳跃性变化的，和\(n,m\)的因子数处于同一个级别，就是\(O(\sqrt{n})\)，我们只要发现下一次值的变化在哪就好了，然后把\(\mu\)数组记录一下前缀和，就从\(O(n)\)优化成\(O(\sqrt{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
| #include<bits/stdc++.h>
#define maxn 50000
using namespace std;
bool vis[50010]={};
int prime[50010]={};
int mu[50010]={};
int sum[50010]={};
int cnt=0;
inline int ReadInt()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
void Init()
{
mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=1;i<=maxn;i++)
{
sum[i]=sum[i-1]+mu[i];
}
}
void work()
{
int a,b,d;
a=ReadInt();
b=ReadInt();
d=ReadInt();
a/=d;
b/=d;
if(a>b) swap(a,b);
int ans=0,pos;
for(int i=1;i<=a;i=pos+1)
{
pos=min(a/(a/i),b/(b/i));
ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i);
}
printf("%d\n",ans);
}
int main()
{
Init();
int T;
T=ReadInt();
while(T--) work();
return 0;
}
|
http://www.lydsy.com/JudgeOnline/problem.php?id=2301 还有一个和上一道及其相似的题目
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
对于询问的\(a,b,c,d\)，我们只需要做一下简单的区间容斥就好了，比较简单
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
75
| #include<bits/stdc++.h>
#define maxn 50000
using namespace std;
bool vis[50010]={};
int prime[50010]={};
int mu[50010]={};
int sum[50010]={};
int cnt=0;
inline int ReadInt()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
void Init()
{
mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
for(int i=1;i<=maxn;i++)
{
sum[i]=sum[i-1]+mu[i];
}
}
int cal(int a,int b)
{
if(a>b) swap(a,b);
int ans=0,pos;
for(int i=1;i<=a;i=pos+1)
{
pos=min(a/(a/i),b/(b/i));
ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i);
}
return ans;
}
void work()
{
int a,b,c,d,k;
a=ReadInt();
b=ReadInt();
c=ReadInt();
d=ReadInt();
k=ReadInt();
int ans=0;
ans+=cal(b/k,d/k);
ans-=cal(b/k,(c-1)/k);
ans-=cal((a-1)/k,d/k);
ans+=cal((a-1)/k,(c-1)/k);
printf("%d\n",ans);
}
int main()
{
Init();
int T;
T=ReadInt();
while(T--) work();
return 0;
}
|
http://www.lydsy.com/JudgeOnline/problem.php?id=2440
小X自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第K个数送给小X。小X很开心地收下了。 然而现在小W却记不起送给小X的是哪个数了。你能帮他一下吗？
首先有一个非常诡异的结论就是这个数的大小不会超过\(3*k\)。（是我试出来的...因为之前的\(2*k\) TLE了...） 然后我们对这个值进行二分查找，我们要求对于一个\(x\)，要迅速的知道\(\le x\)的不讨厌的数有多少个 因为这个题是在全集上面做减法，所以不是很好像之前的题目一样，把问题表述为\(f(x)\)和\(F(x)\) 我们直接观察这个容斥的本质 设\(G(t)\)为\(1 \le i \le x\)中，\(i\)为\(t \times t\)整数倍的\(i\)的个数 那么就是对每个质数\(G(p)\)进行传统的容斥（奇数个质因子减去...偶数个质因子加回来...） 这样的容斥和莫比乌斯函数完全相同！ 那么答案就是\[\sum_{i=2}^{\sqrt{n}}\mu(i)G(i)\] 至于\(G(i)\)怎么计算，非常简单，就是\[\lfloor \frac{x}{i \times i} \rfloor\]
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
| #include<bits/stdc++.h>
#define maxn 1000000
using namespace std;
bool vis[1000010]={};
int prime[1000010]={};
long long mu[1000010]={};
int cnt=0;
void Init()
{
mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
}
long long k;
bool pa(long long x)
{
long long ans=x;
for(long long i=2ll;i<=sqrt(x);i++)
{
ans+=mu[i]*(x/(i*i));
}
if(ans<k) return 1;
return 0;
}
void work()
{
scanf("%lld",&k);
long long l=k,r=3*k;
while(l<r)
{
long long mid=(l+r)/2;
if(pa(mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l);
}
int main()
{
Init();
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}
|