莫比乌斯反演

自用笔记算法

莫比乌斯反演简单应用

线性筛选求莫比乌斯反演函数代码

代码实现

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;  
            }  
        }  
    }  
}

题目一

求给定相同范围内有多少个数对(x,y)满足gcd(x,y)为质数：欧拉函数

分析

代码实现

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
#include <iostream>  
#include <string.h>  
#include <stdio.h>  
#include <bitset>  
using namespace std;  
typedef long long LL;  
const int N = 10000010;  
bitset<N> prime;  
LL phi[N];  
LL f[N];  
int p[N];  
int k;  
void isprime()  
{  
    k = 0;  
    prime.set();  
    for(int i=2; i<N; i++)  
    {  
        if(prime[i])  
        {  
            p[k++] = i;  
            for(int j=i+i; j<N; j+=i)  
                prime[j] = false;  
        }  
    }  
}  
void Init()  
{  
    for(int i=1; i<N; i++)  phi[i] = i;  
    for(int i=2; i<N; i+=2) phi[i] >>= 1;  
    for(int i=3; i<N; i+=2)  
    {  
        if(phi[i] == i)  
        {  
            for(int j=i; j<N; j+=i)  
                phi[j] = phi[j] - phi[j] / i;  
        }  
    }  
    f[1] = 0;  
    for(int i=2;i<N;i++)  
        f[i] = f[i-1] + (phi[i]<<1);  
}   
LL Solve(int n)  
{  
    LL ans = 0;  
    for(int i=0; i<k&&p[i]<=n; i++)  
        ans += 1 + f[n/p[i]];  
    return ans;  
}  
int main()  
{  
    Init();  
    isprime();  
    int n;  
    scanf("%d",&n);  
    printf("%I64d\n",Solve(n));  
    return 0;  
}

注意事项

因为xy可以互换 所以欧拉函数求和乘2即为所求 在加上x和y相等且为素数的情况
即f(n)=phi(1)+phi(2)+···+phi(n) F(n)=2f(n)+1
对于每个素数p[i] 变为n/p[i]带入函数作为右边界

题目二

求不同范围内有多少个数对(x,y)满足gcd(x,y)为质数：莫比乌斯反演

分析

代码实现

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
#include <iostream>  
#include <string.h>  
#include <stdio.h>   
using namespace std;  
typedef long long LL;  
const int N = 10000005;  
bool vis[N];  
int p[N];  
int cnt;  
int g[N],u[N],sum[N];  
void Init()  
{  
    memset(vis,0,sizeof(vis));  
    u[1] = 1;  
    cnt = 0;  
    for(int i=2;i<N;i++)  
    {  
        if(!vis[i])  
        {  
            p[cnt++] = i;  
            u[i] = -1;  
            g[i] = 1;  
        }  
        for(int j=0;j<cnt&&i*p[j]<N;j++)  
        {  
            vis[i*p[j]] = 1;  
            if(i%p[j])  
            {  
                u[i*p[j]] = -u[i];  
                g[i*p[j]] = u[i] - g[i];  
            }  
            else  
            {  
                u[i*p[j]] = 0;  
                g[i*p[j]] = u[i];  
                break;  
            }  
        }  
    }  
    sum[0] = 0;  
    for(int i=1;i<N;i++)  
        sum[i] = sum[i-1] + g[i];  
}  
int main()  
{  
    Init();  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        LL n,m;  
        cin>>n>>m;  
        if(n > m) swap(n,m);  
        LL ans = 0;  
        for(int i=1,last;i<=n;i=last+1)  
        {  
            last = min(n/(n/i),m/(m/i));  
            ans += (n/i)*(m/i)*(sum[last]-sum[i-1]);  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}

cf 803F

题目要求

求给定数组中有多少个任意大小的连续子序列满足互质

分析

统计出1-n中每个数因数的个数 作为函数cnt(x)
f(x)=(2^cnt(x))-1
答案为i=1-10^5求和f(x)*u(x)
u(x)为莫比乌斯函数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define mod 1000000007ll
using namespace std;
int mu[maxn], N, prime[maxn], mark[maxn], cnt[maxn], mi[maxn];
void shai()
{
	int i, j;
	mu[1]=1;
	for(i=2;i<maxn;i++)
	{
		if(!mark[i]){prime[++*prime]=i;mu[i]=-1;}
		for(j=1;i*prime[j]<maxn;j++)
		{
			mark[i*prime[j]]=1;
			if(i%prime[j]==0)break;
			mu[i*prime[j]]=-mu[i];
		}
	}
}
void init()
{
	int i, j, x;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	{
		scanf("%d",&x);
		for(j=1;j*j<=x;j++)if(x%j==0)cnt[j]++, cnt[x/j]+=j!=x/j;
	}
	mi[0]=1;
	for(i=1;i<maxn;i++)mi[i]=(mi[i-1]<<1)%mod;
}
int main()
{
	ll ans=0;
	init();
	shai();
	for(int i=1;i<maxn;i++)ans=(ans+(mi[cnt[i]]-1)*mu[i])%mod;
	printf("%I64d",(ans+mod)%mod);
	return 0;
}
 `

本文标题:莫比乌斯反演

文章作者:Hippopmonkey

发布时间:2017-04-30, 14:50:48

最后更新:2017-04-30, 15:13:14

原始链接:http://xuboming8.github.io/2017/04/30/莫比乌斯反演/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 莫比乌斯反演简单应用
    1. 1.1. 线性筛选求莫比乌斯反演函数代码
      1. 1.1.1. 代码实现
    2. 1.2. 题目一
      1. 1.2.1. 分析
      2. 1.2.2. 代码实现
      3. 1.2.3. 注意事项
    3. 1.3. 题目二
      1. 1.3.1. 分析
      2. 1.3.2. 代码实现
    4. 1.4. cf 803F
      1. 1.4.1. 题目要求
      2. 1.4.2. 分析
      3. 1.4.3. 参考AC代码
|