莫比乌斯函数

发表于
字数统计: 2,381 | 阅读时长 ≈ 11

前言

数论知识…一定是我太菜了所以不敢写莫比乌斯反演…

莫比乌斯函数还是蛮好理解的

侵删

浅析莫比乌斯函数

莫比乌斯看样子很高大上

我们第一次了解到莫比乌斯是在小学时候，那时候书上有个东西叫做莫比乌斯环好像可以折射出很多现实意义

不过我们不会考虑这些现实意义我们来看一下莫比乌斯函数

莫比乌斯反演的引用

我不是很了解这个东西…
我们先来看一下一些式子

我们设 f(x), g(x) 为定义在正整数集合上的两个函数，满足

∑d|ng(d)

我们将就看一下
根据定义，我们可以知道
$\sum$

根据 f(n) 推出 g(n)

我们继续观察，发现以下规律（依旧拉图片…

上面的？部分与 d 没有直接关系，而是与 n/d 有关，是n/d 对应的某个函数值,记为 μ（n/d），我们称这个函数为莫比乌斯函数，在解决 gcd 问题上很有帮助

反演？

我们看一下观察出来的规律

我们令

也可以写成

因此我们把下式称之为莫比乌斯反演

观察前面的例子，我们可以找到部分莫比乌斯函数的值

所以我们来看一下 μ（d）的定义

  1. 若d=1，则 μ（d）=1
  2. 若d=p1·p2·p3·…·pk，其中 p(0<=i<=k)为互异的素数，则 μ(d) =(-1)k
  3. 对于其余情况 μ(d)=0

我们再来看几个莫比乌斯函数的性质

好了就这样随便看看好了不给证明

综上所述，莫比乌斯反演就是指一下式子…

怎么用我也不怎么会…

我们再来看一下他的两种变形（全部自己去证（我菜啊逃~

还有一个反演的性质

这种东西记记好了考试又不会给自己证…
另外很多关于数论的题目只用莫比乌斯是不够的可能还要加上数论分块…

线性求莫比乌斯函数

所以我们稀里糊涂讲了那么多，来看一下怎么用线性的时间求出莫比乌斯函数

我们已经知道， μ（n）是积性函数，所以可以用类似欧拉筛的方式在线性的时间内求出莫比乌斯函数

莫比乌斯函数要么是0要么是1要么是-1，而且判断这个数对应的莫比乌斯函数在它的性质里也讲过了，因此，在欧拉筛的基础上，我们求莫比乌斯函数就很方便了…

口糊了那么多，直接看代码好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isprime[10000010];
int cnt=0,prime[5000010],mu[10000010];
inline void init(int x){
	memset(isprime,1,sizeof(isprime));
	mu[1]=1;
	for(register int i=2;i<=x;i++){
		if(isprime[i]){
			prime[++cnt]=i;mu[i]=-1;
		}
		for(register int j=1;j<=cnt;j++){
			long long t=prime[j]*i;
			if(t>x) break;
			isprime[t]=0;
			if(i%prime[j]==0){
				mu[t]=0;break;
			}
			else mu[t]=-mu[i];
		}
	}
}

整体上看是和欧拉筛差不多的…

另外在做莫比乌斯的题目时，我们要灵活应用反演变化，用反演把时间复杂度降低。对于一些很难求的东西，我们可以先求出简单的东西，再反演推导到我们要求的东西上

从网上找了四个要点…

公式推导：利用莫比乌斯反演推导出基本式子

等价变换：变量替换，内层外移等技巧

线性筛法：线性筛法功能强大，可以根据需要预处理各种信息

分块处理：归结到最后，通过分块处理在根号n内实现

具体内容还是在题目里见吧

题目

BZOJ1101

题目描述

　　
FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a
，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

输入

　　第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个
正整数，分别为a,b,d。（1<=d<=a,b<=50000）

输出

　　对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。

样例输入
2
4 5 2
6 4 3
样例输出
3
2

//对于第一组询问，满足条件的整数对有(2,2)，（2,4），（4，2）。对于第二组询问，满足条件的整数对有（
6,3），（3,3）。

解题分析

很接近板子题
先预处理每个数的莫比乌斯函数值
设f(i)=gcd(x,y)=i的数对个数，所求即为f(1)
构造一个和它满足莫比乌斯反演的函数 F= gcd(x,y)=i的倍数 的数对个数
然后我们可以得到反演方程（makedown不能打\sum…望体谅
另外一个函数的值还是很好求的。。。
进行求前缀和和数论分块…
如果不这样做的话只有70分
所以重要的东西代码里见

AC代码4164ms
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
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>

using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=50010;
int k,cnt=0;
bool isprime[N];
int prime[N],mu[N],sum[N];

inline void init(int x){
    memset(isprime,1,sizeof(isprime));
    mu[1]=1;
    for(register int i=2;i<=x;i++){
        if(isprime[i]){
            prime[++cnt]=i;mu[i]=-1;
        }
        for(register int j=1;j<=cnt;j++){
            long long t=prime[j]*i;
            if(t>x) break;
            isprime[t]=0;
            if(i%prime[j]==0){
                mu[t]=0;break;
            }
            else mu[t]=-mu[i];
        }
    }
    for(register int i=1;i<=x;i++) sum[i]=sum[i-1]+mu[i];
}

int main(){
    k=read();
    init(N);
    while(k--){
        static long long a,b,d;
        a=read();b=read();d=read();
        static long long max_rep,ans;
        max_rep=min(a,b);ans=0;
        for(long long l=1,r;l<=max_rep;l=r+1)
        {
            r=min(a/(a/l),b/(b/l));
            ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

HAOI2011 Problem B

题目描述

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

输入输出格式
输入格式：

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

输出格式：

共n行，每行一个整数表示满足要求的数对(x,y)的个数

输入输出样例
输入样例#1：
2
2 5 1 5 1
1 5 1 5 2
输出样例#1：
14
3
说明

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

解题分析

只能说跟上次差不多
也是一道很基础的连莫比乌斯函数的题
继续构造莫比乌斯反演的函数
但是这道题我们用到了容斥原理
就是那些学生参加各种兴趣小组类型的题目，问一共会有多少个学生什么什么的
小学的奥数题成为oi的元素也是一番趣味
求题目中的个数，就是求出ans=(b,d)-(a-1,d)-(c,b-1)+(a-1,b-1)
就是每询问一次要做类似的操作四次
也是要加上数论分块和前缀和的不然会T
不多比比上代码

AC代码11980ms
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
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define re register int
#define ll long long 

using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=50010;
int n,a,b,c,d,k,cnt=0;
int pri[N],mu[N];
bool isp[N];
ll sum[N];

inline void init(){
    mu[1]=1;
    for(re i=2;i<=N;i++){
        if(!isp[i]){
            pri[++cnt]=i;mu[i]=-1;
        }
        int t;
        for(re j=1;(t=pri[j]*i)<=N&&j<=cnt;j++){
            isp[t]=1;
            if(i%pri[j]==0){
                mu[t]=0;break;
            }
            else mu[t]=-mu[i];
        }
    }
    for(re i=1;i<=N;i++) sum[i]=sum[i-1]+mu[i];
}

inline ll solve(ll n,ll m){
    n/=k; m/=k;
    if(n>m) swap(n,m); if(n==0) return 0;
    ll i,next1,next2,next;
    ll tot=0;
    for(i=1;i<=n;i=next) {
        next1=n/(n/i); next2=m/(m/i);
        next=min(next1,next2);
        tot+=(n/i)*(m/i)*(sum[next]-sum[i-1]);
        next++;
    }
    return tot;
}


int main(){
    n=read();
    init();
    while(n--){
        a=read();b=read();c=read();
        d=read();k=read();
        ll ans=solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1);
        printf("%lld\n",ans);
    }
    return 0;
}

后记

这玩意还是比较深奥的在高层次的oi中也是很重要的一个考点
所以我很菜看了很久反演也不会导
这篇文章我应该是说写的很潦草了…
算了算了重要的东西在就行了
欢迎指正联系方式如下…

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan