莫比乌斯反演在数论中占有重要的地位，许多情况下能大大简化运算。那么我们先来认识莫比乌斯反演公式。
定理：
和是定义在非负整数集合上的两个函数，并且满足条件，那么我们得到结论
在上面的公式中有一个函数，它的定义如下：
（1）若，那么
（2）若，均为互异素数，那么
（3）其它情况下
对于函数，它有如下的常见性质：
（1）对任意正整数有
（2）对任意正整数有
线性筛选求莫比乌斯反演函数代码。
void Init() { memset(vis,0,sizeof(vis)); mu[1] = 1; cnt = 0; for(int i=2; i
有了上面的知识，现在我们来证明莫比乌斯反演定理。
证明
证明完毕！
嗯，有了莫比乌斯反演，很多问题都可以简化了，接下来我们来看看莫比乌斯反演在数论中如何简化运算的。
题目：http://bz.cdqzoi.com/JudgeOnline/problem.php?id=2818
题意：给一个正整数，其中，求使得为质数的的个数，。
分析：对于本题，因为是使得为质数，所以必然要枚举小于等于的质数，那么对于每一个质数，只
需要求在区间中，满足有序对互质的对数。
也就是说，现在问题转化为：在区间中，存在多少个有序对使得互质，这个问题就简单啦，因为
是有序对，不妨设，那么我们如果枚举每一个，小于有多少个与互素，这正是欧拉函数。所以
我们可以递推法求欧拉函数，将得到的答案乘以2即可，但是这里乘以2后还有漏计算了的，那么有哪些呢？
是且为素数的情况，再加上就行了。
代码：
#include
#include
#include
#include
using namespace std; typedef long long LL; const int N = ; bitset
prime; LL phi[N]; LL f[N]; int p[N]; int k; void isprime() { k = 0; prime.set(); for(int i=2; i
>= 1; for(int i=3; i
嗯，上题不算太难，普通的欧拉函数就可以搞定，接下来我们来看看它的升级版。
题意：给定两个数和，其中，，求为质数的有多少对？其中和的范
围是。
分析：本题与上题不同的是和不一定相同。在这里我们用莫比乌斯反演来解决，文章开头也说了它能大大简化
运算。我们知道莫比乌斯反演的一般描述为：
其实它还有另一种描述，本题也是用到这种。那就是：
好了，到了这里，我们开始进入正题。。。
对于本题，我们设
为满足且和的的对数
为满足且和的的对数
那么，很显然，反演后得到
因为题目要求是为质数，那么我们枚举每一个质数，然后得到
如果直接这样做肯定TLE，那么我们必须优化。
我们设，那么继续得到。
到了这里，可以看出如果我们可以先预处理出所有的对应的的值，那么本题就解决了。
我们设，注意这里为素数，。
那么，我们枚举每一个，得到，现在分情况讨论：
（1）如果整除，那么得到
（2）如果不整除，那么得到
#include
#include
#include
using namespace std; typedef long long LL; const int N = ; 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>>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<
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199899.html原文链接：https://javaforall.net
