数论-莫比乌斯反演入门题

数论-莫比乌斯反演入门题

1.​​题目连接​​​这个题目可以使用容斥来写，也可以使用莫比乌斯反演来演。我们先看一下如何用莫比乌斯反演来解决这个问题。 2.首先我们需要知道一些结论[1,a],[1,b]这个二维的区间里gcd（i,j)=k以及k的倍数的（i，j）的个数是(a/k)*(b/k)个。知道了这个，那么我们这个题目的意思就是给你一个上述的区间，让你求出gcd(i,j)=k的i，j有多少对。这个和我们的结论有点区别，这个是让我们求精确的gcd(i,j)=k,而不是k的倍数。我们回忆一下反演的作用，其实就是求某个精确的不好求，我们可以把总的求出来，然后通过反演的的某个精确的函数。这里需要自己脑补一下这里精确的定义。那么我们这里就很显然了，我们知道求gcd(i,j)=k的倍数在这个区间里是很简单的，但是求等于k却不容易。所以使用反演的思想就很容易的得到下边的式子：

那么就很简单的可以求出答案了，但是这里有一个问题就是重复的问题：gcd(i,j)=gcd(j,i)，所以这里还是要去重。所以再来看这个题目很容易的就会知道这就是一个考察反演得作用的一道题目，如果对反演理解的到位，那么很容易就会想到解法。

代码如下：

#include"stdafx.h"#include#include#include#include#include#pragma warning(disable:4996)using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define ll long long#define pb push_back#define gcd __gcdconst double EPS = 1e-8;const int maxn = 1e5 + 1000;const int inf = 0x3f3f3f3f;const double PI = acos(-1.0);bool check[maxn];int prime[maxn];int mu[maxn];void Moblus() { cl(check, false); mu[1] = 1; int tot = 0; for (int i = 2; imaxn)break; check[i*prime[j]] = true; if (i%prime[j] == 0) { mu[i*prime[j]] = 0; break; } else mu[i*prime[j]] = -mu[i]; } }}int main() { int T; scanf("%d", &T); Moblus(); int cas = 1; while (T--) { int a, b, c, d, k; scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); if (k == 0) { printf("Case %d: 0\n", cas++); continue; } ll ans1 = 0; b /= k; d /= k; if (b>d)swap(b, d); for (int i = 1; i <= b; i++)ans1 += (ll)mu[i] * (b / i)*(d / i); ll ans2 = 0; for (int i = 1; i <= b; i++)ans2 += (ll)mu[i] * (b / i)*(b / i); ans2 >>= 1; printf("Case %d: %lld\n", cas++, ans1 - ans2); } return 0;}

这样推出来看上去很合情合理，但是，有一个问题。就是那个F函数，我们推理得全部过程都是基于一个观点，我们上来就知道设计了F函数，然而实际上，我们上来不一定就能够找到F函数，或者说问题得难点就在于如何寻找这个F函数。其实很多时候，如果没有特别强的直觉，这个F函数你是找不到的。所以很多人对着这个例题学习，认为自己学会了莫比乌斯反演，其实不然。所以我们还是需要从本质出发，正向推导。

这才是真的正向推理，虽然路径不同，但是殊途同归。代码还是不变，可能会有疑问：如何去重？画个矩阵就可以知道了。代码还是不变的。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。