莫比乌斯反演

莫比乌斯反演在数论中占有重要的地位,许多情况下能大大简化运算。那末我们先来认识莫比乌斯反演公式。

 

定理:是定义在非负整数集合上的两个函数,并且满足条件,那末我们得到结论

 

     

 

在上面的公式中有1个函数,它的定义以下:

 

    (1)若,那末

    (2)若均为互异素数,那末

    (3)其它情况下

 

 

函数,它有以下的常见性质:

 

    (1)对任意正整数

  

                            

 

        (2)对任意正整数

 

         

 

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

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] = ⑴;
}
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;
}
}
}
}

有了上面的知识,现在我们来证明莫比乌斯反演定理。

 

证明

 

 

证明终了!

 

嗯,有了莫比乌斯反演,很多问题都可以简化了,接下来我们来看看莫比乌斯反演在数论中如何简化运算的。

 

 

题目:http://bz.cdqzoi.com/JudgeOnline/problem.php?id=2818

 

题意:给1个正整数,其中,求使得为质数的的个数,

 

分析:对本题,由于是使得为质数,所以必定要枚举小于等于的质数,那末对每个质数,只

     需要求在区间中,满足有序对互质的对数。

 

     也就是说,现在问题转化为:在区间中,存在多少个有序对使得互质,这个问题就简单啦,由于

     是有序对,无妨设,那末我们如果枚举每个,小于有多少个互素,这正是欧拉函数。所以

     我们可以递推法求欧拉函数,将得到的答案乘以2便可,但是这里乘以2后还有漏计算了的,那末有哪些呢?

     是且为素数的情况,再加上就好了。

 

代码:

#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⑴] + (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
",Solve(n));
return 0;
}

嗯,上题不算太难,普通的欧拉函数就能够弄定,接下来我们来看看它的升级版。

 

题意:给定两个数,其中,求为质数的有多少对?其中的范

     围是

 

分析:本题与上题不同的是不1定相同。在这里我们用莫比乌斯反演来解决,文章开头也说了它能大大简化

     运算。我们知道莫比乌斯反演的1般描写为:

 

     

 

     其实它还有另外一种描写,本题也是用到这类。那就是:

 

     

 

     好了,到了这里,我们开始进入正题。。。

 

     对本题,我们设

 

     为满足的对数

     为满足的对数

 

     那末,很明显,反演后得到

 

     由于题目要求是为质数,那末我们枚举每个质数,然后得到

 

     

 

     如果直接这样做肯定TLE,那末我们必须优化。

 

     我们设,那末继续得到

 

     到了这里,可以看出如果我们可以先预处理出所有的对应的的值,那末本题就解决了。

 

     我们设,注意这里为素数,

 

     那末,我们枚举每个,得到,现在分情况讨论:

 

     (1)如果整除,那末得到

 

       

 

     (2)如果不整除,那末得到

 

       

#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] = ⑴;
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⑴] + 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⑴]);
}
cout<<ans<<endl;
}
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 莫比乌斯反演

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡