POI 2007 ZAP - 莫比乌斯反演

作者: 苏子旃 | 来源:发表于2019-02-13 17:31 被阅读0次

POI 2007 ZAP - 莫比乌斯反演
莫比乌斯反演
莫比乌斯反演+模板
莫比乌斯反演-从基础开始
莫比乌斯反演-2-拓展形式
莫比乌斯反演-奇妙的欧拉
2019-05-21 莫比乌斯反演函数
LUOGU 2257 YY的GCD - 莫比乌斯反演
神奇的莫比乌斯带
莫比乌斯

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

Input Format
第一行一个正整数 $N$ ，表示询问组数。
接下来 $N$ 行，每行 $3$ 个正整数 $a,b,d$ ，含义如题目所示意。

Output Format
对于每个询问输出一行表示答案。

Sample Input

2
4 5 2
6 4 3

Output Format

3
2

Constraints
对于 $100$ %的数据，满足 $1 \leq N \leq 50000,1 \leq d \leq a,b \leq 50000$ 。

CCYOS
这是一道莫比乌斯反演的板子题。

前置技能

符号	含义
$a \mid b$	$a$ 被 $b$ 整除
$P$	质数集合
$\omega (n)$	$n$ 的不同质因数个数
$\phi (n)$	$[1,n - 1]$ 内与n互质的数的个数`显然n和本身不互质`
$\mu(u)$	莫比乌斯函数，详见下文
$\epsilon$	狄利克雷卷积单位元
$1(n)$	对于任意 $n \in N*$ ， $1(n) = 1$ ，乘法单位元
$Id(n)$	对于任意 $n \in N*,Id(n) = n$
$[P]$	命题 $P$ 成立， $[P] = 1$ ；反之为 $0$

概念	含义
数论函数	定义域为全体正整数，值域为复数域子集的函数。
积性函数	若 $gcd(a,b) = 1$ ，则 $f(a) \times f(b) = f(ab)$
完全积性函数	对于任意 $a,b$ ，都有 $f(a) \times f(b) = f(ab)$

莫比乌斯函数
$\mu(n) = \begin{cases} 1………… n = 1 \\ (-1)^{\omega(n)} …\forall k_i = 1\\ 0 …………other \end{cases}$ 其中， $k_i$ 表示每一个质因数的次数。 $n = p_1^{k_1}·p_2^{k_2}·……·p_{\omega(n)}^{k_{\omega(n)}}$
一个重要的性质 $\sum_{d \mid n}\mu(d) = [n = 1]$

证明如下：
1）当 $n = 1$ 时:显然 $[n = 1] = 1$ 。可枚举的约数 $d$ 只有 $1$ ，则原式 = $\mu(1)$ = $1$ = $[ n = 1]$ 。
2）当 $\forall k_i = 1$ 时:显然此时 $n > 0$ ， $[n = 1] = 0$ 。 $n = p_1^{k_1}·p_2^{k_2}·……·p_{\omega(n)}^{k_{\omega(n)}}$ 则约数 $d = p_1^{k'_1}·p_2^{k'_2}·……·p_{\omega(n)}^{k'_{\omega(n)}}$ 因为 $\forall k_i = 1$ ，所以 $\forall k'_i \in [0,1]$ 。不难看出，枚举 $n$ 的约数，即枚举取的质因数的乘积即可。根据 $\mu$ 的定义，有 $\sum_{d \mid n} \mu(d) = \sum_{i = 1}^{\omega(n)} C_{\omega(n)} ^ {i} · (-1)^i$ 根据二项式定理 $(x + y)^k = \sum_{i = 0}^{n}C_{n}^{i}·x^iy^{n - i}$ 构造可得 $\sum_{d \mid n} \mu(d) = \sum_{i = 1}^{\omega(n)} C_{\omega(n)} ^ {i} · (-1)^i·1^{n - i} = (1 - 1)^{\omega(n)} = 0$ 即此时原式恒为0。
3）定义域内 $(n > 0)$ 其他情况:即在第二种情况上添加 $add = \sum\mu(d),d|n且\exists k'_i > 1$ ，据定义有 $add = 0$ 。所以此时原式恒为0。
证毕。

get_mu函数的写法

inline void get_mu(int N){
    miu[1] = 1;//初始化
    for(int i = 2;i <= N;++i){//从2开始
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;//标记质数，质数只有两个约数所以质数的miu值一定是-1
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;//标记合数
            if(!(i % prime[j]))break;//避免标记到存在ki >= 2的数
            else miu[i * prime[j]] = -miu[i];//多了一个质因数,(-1)^k要取相反
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];//前缀和便于计算
}

狄利克雷卷积
$f*g = \sum_{d \mid n}f(d) · g(\frac{n}{d})$ 满足交换率，结合率，分配律。
两个积性函数的卷积一定是积性函数。

$\mu * 1 = \epsilon$
单位元 $\epsilon$ 的是满足 f * e = f的函数，当 e = [n = 1]时，这个条件成立，所以这种定义是满足条件的定义之一。而且很好记。

证明： $\mu * 1 = \sum_{d \mid n}\mu(d)·1(\frac{n}{d}) = \sum_{d \mid n}\mu(d) = [n = 1] = \epsilon$
证毕

欧拉函数
一个重要的性质
$\sum_{d \mid n} \varphi(d) = n$

证明：
咕咕咕。不会证。

推论
1） $\phi * 1 = Id$

证明：
$Id(n) = n = \sum_{d \mid n} \phi(d) = \sum_{d \mid n} \phi(d)·1(\frac{n}{d}) = 1 * \phi$ 证毕

2） $\phi = Id * \mu$

证明：
由5.1.推出 $\phi * 1 * \mu= Id * \mu$ 狄利克雷卷积满足结合律，所以 $\phi *( 1*\mu) = Id * \mu$ 由4.可得 $\phi * \epsilon = Id * \mu = \phi$ 证毕

莫比乌斯反演
当 $f(n) = \sum_{d \mid n}g(d)$ 必然有 $g(n) = \sum_{d \mid n}f(\frac{n}{d})·\mu(d)$ 假设和结果互换，此仍然为真命题。

证明如下：
构造转化假设，有 $f(n) = \sum_{d \mid n}g(d)·1(\frac{n}{d}) = g*1$
则转为证明：若 $f = g*1,$ 则 $g = f * \mu$ 。
与5.2.证明相类似，由假设得到 $f*\mu = g * (1 * \mu)$ 由4.得 $f * \mu = g * \epsilon = g$
反之证若 $g = f * \mu,$ 则 $f = g*1$ : $g * 1 = f * (u * 1)$ $g * 1 = f * \epsilon$ $g * 1 = f$ 证毕

一些常见的推论
1） $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_{d}\mu(d)·\lfloor \frac{n}{d} \rfloor · \lfloor \frac{m}{d} \rfloor$

证明:
由莫比乌斯函数的性质可得 $[gcd(i,j) = 1] = \sum_{d \mid gcd(i,j)}\mu(d)$ 代入原式可得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_{i}\sum_{j}\sum_{d \mid gcd(i,j)}\mu(d)$ 因为 $d \mid gcd(i,j)$ ，所以 $d \mid i,d \mid j$ ，故考虑先枚举 $d$ ，再枚举 $i,j$ ，可得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_{d}\mu(d)\sum_{i}^{\lfloor \frac{n}{d} \rfloor}\sum_{j}^{\lfloor \frac{m}{d} \rfloor}1$ 把后面一段废话化简得 $\sum_{i}\sum_{j}[gcd(i,j) = 1] = \sum_{d}\mu(d)·\lfloor \frac{n}{d} \rfloor · \lfloor \frac{m}{d} \rfloor$ 证毕

2） $\sum_{i}\sum_{j}[gcd(i,j) = k] = \sum_{d}\mu(d)·\lfloor \frac{n}{kd} \rfloor · \lfloor \frac{m}{kd} \rfloor$

证明：
将原式转化为 $\sum_{i}\sum_{j}[gcd(\frac{i}{k},\frac{j}{k}) = 1]$ 依照6.1.的证明。
证毕

3） $\sum_{i}\sum_{j}gcd(i,j) = \sum_{d}\phi(d)·\lfloor \frac{n}{d} \rfloor · \lfloor \frac{m}{d} \rfloor$

证明：
由5.1可得 $Id(gcd(i,j)) = \sum_{d \mid gcd(i,j)}\phi(d) · 1(\frac{gcd(i,j)}{d}) =\sum_{d \mid gcd(i,j)}\phi(d)$ 代入原式中可得 $\sum_{i}\sum_{j}gcd(i,j) = \sum_{i}\sum_{j}\sum_{d \mid gcd(i,j)}\phi(d)$ 依照6.1.证明。
证毕

一般做法
根据题意列出算式。
列出一个可以反演的方程。
反复化简，向 $\mu$ 函数靠拢。
计算。

小技巧：整除分块
通过观（da）察（biao）发现，在处理 $\sum_{i}\frac{n}{i}$ 的过程中，会出现很多相同的结果，而且这些结果呈块状分布。进一步观（da）察（biao），会发现对于每一个结果相同的块，当前位置为 $i$ ,这个块的结束位置为 $\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$ 。
那么整除分块的代码就很好写了：

for(int l = 1,r;l <= n;l = r + 1){
  r = n/(n/l);  
  一些操作;
}

在GC的帮助下找到了理解这个问题的另一个思路：LUOGU 1403 感谢！！！

code

#include<bits/stdc++.h>
using namespace std;

#define mxn 50005
int N,cnt;
int sum[mxn],prime[mxn],vis[mxn],miu[mxn];

inline int read(){
    int ret = 0,fl = 1;
    char c = getchar();
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void get_mu(int N){
    miu[1] = 1;
    for(int i = 2;i <= N;++i){
        if(!vis[i])prime[++cnt] = i,miu[i] = -1;
        for(int j = 1;j <= cnt&&prime[j] * i <= N;++j){
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))break;
            else miu[i * prime[j]] = -miu[i];
        }
    }
    for(int i = 1;i <= N;++i)sum[i] = sum[i - 1] + miu[i];
}

int main(){
    N = read();
    get_mu(50000);
    for(int i = 1;i <= N;++i){
        int a,b,k;
        long long ans = 0;
        a = read();b = read();k = read();
        int limit = min(a,b);
        for(int l = 1,r;l <= limit;l = r + 1){
            r = min(a/(a/l),b/(b/l));
            ans += 1ll * (a/(l * k)) * (b/(l * k)) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

参考文档

POI 2007 ZAP - 莫比乌斯反演
LUOGU 3455DescriptionFGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数和，有多...
莫比乌斯反演
适用题目特征常见和式常见和式常见和式常见和式其中表示的约数个数。常见和式原理例题 Luog...
莫比乌斯反演+模板
链接https://www.lydsy.com/JudgeOnline/problem.php?id=2301
莫比乌斯反演-从基础开始
提示：别用莫比乌斯反演公式，会炸的只需要记住： [gcd(i,j)=1]=\sum_{d|gcd(i,j)}\m...
莫比乌斯反演-2-拓展形式
设的定义域是大于等于 1 的实数。如果，，那么。这被称作是莫比乌斯反演的拓展形式。通过简单的代入演算可以知...
莫比乌斯反演-奇妙的欧拉
让我们从一道题开始求\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j),(n 首先对gcd...
2019-05-21 莫比乌斯反演函数
LUOGU 2257 YY的GCD - 莫比乌斯反演
Description神犇YY虐完数论后给kAc出了一题:给定求且为质数的有多少对。kAc不想做，并把这道题扔给了...
神奇的莫比乌斯带
1848年，德国数学家莫比乌斯创造出“莫比乌斯带”，至今已有160余年的历史了。莫比乌斯带是用一张长方形的纸带扭...
莫比乌斯
整顿好行李，我看了看窗外，天空蔚蓝还不乏几片云朵，时值八月盛夏，阳光难得温暖和煦。我瞥了眼时钟，走出旅馆。步行不...

POI 2007 ZAP - 莫比乌斯反演

相关文章

POI 2007 ZAP - 莫比乌斯反演

莫比乌斯反演

莫比乌斯反演+模板

莫比乌斯反演-从基础开始

莫比乌斯反演-2-拓展形式

莫比乌斯反演-奇妙的欧拉

2019-05-21 莫比乌斯反演函数

LUOGU 2257 YY的GCD - 莫比乌斯反演

神奇的莫比乌斯带

莫比乌斯

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读