先整理几个重要的数论函数。
1.莫比乌斯函数
$\mu(n) $ 当\(n=1\)时取1 ，当\(n\)存在平方因子的时候取0 ，否则取\((-1)^k\)，其中\(k\)是\(n\)所含的质因子数量。
2.欧拉函数
\(\phi(n)=\displaystyle\sum_{d=1}^n[gcd(d,n)=1]\)，就是小于等于n且与\(n\)互质的数字的数量。
3.因子函数
\(\sigma (n)\)表示 \(n\)的所有的因子的和
\(\sigma(n)=\displaystyle\sum_{d|n} d\)
还有一个小的\(\epsilon(n)=[n=1]\)
前两个都是积性函数。
接下来是几个重要的反演结论
\[\epsilon(n)=\displaystyle\sum_{d|n}\mu(d) \]\[n=\displaystyle\sum_{d|n}\phi(d) \]\[\sigma(n)=\displaystyle\sum_{d|n}d \]我们使用这三个式子的目的是把目标式转化为可求的东西。比如莫比乌斯函数，或者是因子和之类的东西。
来看看例题就知道了。这些例题其实就是基本模型。
例一、求\(\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m[gcd(i,j)=1]\)的值
其实就是\(\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m\epsilon (gcd(i,j))\)，那么根据第一个式子，可以变化为\(\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m\displaystyle\sum_{d|gcd(i,j)}\mu(d)\)
而，\(d|gcd(i,j)\)有可以表述为\(d|i\)且\(d|j\)，那么我们就先枚举\(d\)，然后再枚举所有的\(i\)和\(j\)，假如 \(d|i\)和\(d|j\)同时成立再加上答案。
那么式子就会变为\(\displaystyle\sum_{d}^{min(n,m)}\mu(d)\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}([d|i]*[d|j])\)
再然后，可以发现\(d|i\)这一项和最后的一重循环\(j\)一点关系没有，于是可以把式子转化为\(\displaystyle\sum_{d}^{min(n,m)}\mu(d)(\displaystyle\sum_{i=1}^{n}[d|i])\displaystyle(\sum_{j=1}^{m}[d|j])\)
那其实这后面两个就好算了，\(\displaystyle\sum_{i=1}^{n}[d|i]\)，这个式子对于确定的\(d\)本质就是在小于等于\(n\)的所有数字是\(d\)的倍数的数字的个数。这就等于\(\lfloor\frac{n}{d}\rfloor\)
所以上式变为\(\displaystyle\sum_{d}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\)，莫比乌斯函数可以快速的计算，后面两个东西可以通过数论分块来在\(O(sqrt(n)\times sqrt(m))\)的时间内解决。总时间复杂度就是这个\(O(\sqrt{nm})\) (吧？) 。
就这题来看，主要运用的就是下面循环的整除。这个整除能够搞事情，现在看到的就是\(d|gcd(i,j)\)，可以转化为\([d|i]*[d|j]\)，比较典型？（因为我之前想不到
还有非常重要的，虽然这属于公式推导的内容。就是循环顺序的调换规则，正常情况下是不会去动的，但是绝大多数时候如果是涉及式子的题目，特别是数学和多项式一类的，循环顺序是非常重要的，因为一般只有最后一个循环好进行操作，循环套循环是非常难套公式和变换的。
而这个法则我一般都是感性理解去操作的，像这里就是，调换过后式子变化挺大，但是这个调换顺序是最关键的一步。要能够意识到调换顺序后的是可以直接计算的。其实只要满足最后一个循环的底下的条件是\(d|gcd(i,j)\)或者等价形式就能够做到，当然\(\mu(d)\)只能是和\(i,j\)无关的函数。
例二、给定两个数组\(a,b\)，求\(\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^mgcd(a_i,b_j)\)。
还是，沿着上一个的思路，利用\(n=\displaystyle\sum_{d|n}\phi(d)\)，创造\(n=\displaystyle\sum_{d|gcd}\)的结构，因为前面两个都是正常的循环，这样可以非常方便的帮助我们解决换顺序的问题。
这样就会变成\(\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^m\displaystyle\sum_{d|gcd(a[i],b[j])}\phi(d)\),然后调换顺序 \(\displaystyle\sum_{d}\phi(d)\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^m[d|a_i][d|b_j]\)
然后还是把\([d|a_i]\)放到前面，\(\displaystyle\sum_{d}\phi(d)(\displaystyle\sum_{i=1}^{n}[d|a_i])(\displaystyle\sum_{j=1}^m[d|b_j])\)
然后后面这两甚至不用整数分块。比上题还好写。
例三、给定两个数组\(a,b\)，求\(\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=i+1}^n[gcd(a_i,a_j)=1]\)。
用\(\epsilon(n)=\displaystyle\sum_{d|n}\mu(d)\)替换后面的部分，得到\(\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=i+1}^n\displaystyle\sum_{d|gcd(a_i,a_j)}\mu(d)\)
然后和上面一样枚举\(d\)把\(\mu(d)\)提前，得到\(\displaystyle\sum_{d}^{n}\mu(d)\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=i+1}^{n}[d|a_i][d|a_j]\)，然后把\([d|a_i]\)提前，得到\(\displaystyle\sum_{d}^{n}\mu(d)\displaystyle\sum_{i=1}^n[d|a_i]\displaystyle\sum_{j=i+1}^{n}[d|a_j]\)
式子到这里就够了，直接对于每个\(d\)统计有多少个\(a_i\)满足\([d|a_i]\)即可。然后就是组合数。
这些都是最基础的模型了。
[POI2007] ZAP-Queries
题目描述
密码学家正在尝试破解一种叫 BSA 的密码。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 \(a,b,d\)，求满足 \(1 \leq x \leq a\)，\(1 \leq y \leq b\)，且 \(\gcd(x,y)=d\) 的二元组 \((x,y)\) 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。
输入格式
输入第一行一个整数 \(n\)，代表要回答的问题个数。
接下来 \(n\) 行，每行三个整数 \(a,b,d\)。
输出格式
对于每组询问，输出一个整数代表答案。
样例 #1
样例输入 #1
2
4 5 2
6 4 3
样例输出 #1
3
2
提示
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 5 \times 10^4\)，\(1 \leq d \leq a,b \leq 5 \times 10^4\)。
其实就是求\(\displaystyle\sum_{i=1}^{a}\displaystyle\sum_{j=1}^b[gcd(i,j)=d]\),也就是\(\displaystyle\sum_{i=1}^{a}\displaystyle\sum_{j=1}^b[\frac {gcd(i,j)}{d}=1]\)
再变形为\(\displaystyle\sum_{i=1}^{a}\displaystyle\sum_{j=1}^b\displaystyle\sum_{D|\frac {gcd(i,j)}{d}}\mu(D)\)，把\(\mu(D)\)提前，枚举\(D\)，\(\displaystyle\sum_{D}^{\lfloor\frac{max(a,b)}{d}\rfloor}\mu(D)\displaystyle\sum_{i=1}^a\displaystyle\sum_{j=1}^b[D\times d |gcd(i,j)]\)
\(\displaystyle\sum_{D}^{\lfloor\frac{max(a,b)}{d}\rfloor}\mu(D)\displaystyle\sum_{i=1}^a[D\times d |i]\displaystyle\sum_{j=1}^b[D\times d|j]\)，然后就是统计\(\displaystyle\sum_{i=1}^a[D\times d |i]\)，其实就是\(\lfloor\frac{a}{D\times d}\rfloor\)
那么最终的式子就是\(\displaystyle\sum_{D}^{\lfloor\frac{max(a,b)}{d}\rfloor}\mu(D)\lfloor\frac{a}{D\times d}\rfloor\lfloor\frac{b}{D\times d}\rfloor\)
单次就是\(O(a)\),总体\(O(n\ max(a,b))\)，会T，后面前面的部分直接筛出来，然后后面的部分要用整除分块优化，可以达到\(O(n\sqrt{max(a,b)})\)
然后就可以写了
YY的GCD
题目描述
神犇 YY 虐完数论后给傻× kAc 出了一题
给定 \(N, M\)，求 \(1 \leq x \leq N\)，\(1 \leq y \leq M\) 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对。
输入格式
第一行一个整数 \(T\) 表述数据组数。
接下来 \(T\) 行，每行两个正整数，\(N, M\)。
输出格式
\(T\) 行，每行一个整数表示第 \(i\) 组数据的结果。
样例 #1
样例输入 #1
2
10 10
100 100
样例输出 #1
30
2791
提示
\(T = 10^4\)，\(N, M \leq 10^7\)。
先简单转化一下，这个形式还是没法直接反演的。
要求为质数，其实就是\(\sigma(i)=i+1\)，所以直接用这个表示\(\displaystyle\sum_{i=1}^{N}\displaystyle\sum_{j=1}^{M}[\sigma(gcd(i,j))=gcd(i,j)+1]\)
这个嵌套...拆不出来吧...
思路错了，之前都是枚举\(Gcd\)的值，这里也直接枚举就没问题了。。。
\(\displaystyle\sum_{k\in {prime}}^{max(N,m)}\displaystyle\sum_{i=1}^{N/k}\displaystyle\sum_{j=1}^{M/k}[gcd(i,j)=1]\)
\(\displaystyle\sum_{k\in {prime}}^{max(N,m)}\displaystyle\sum_{i=1}^{N/k}\displaystyle\sum_{j=1}^{M/k}\displaystyle\sum_{d|gcd(i,j)}\mu(d)\)
\(\displaystyle\sum_{k\in {prime}}^{max(N,m)}\displaystyle\sum_{d}^{\lfloor\frac{N}{k}\rfloor}\mu(d)\displaystyle\sum_{i=1}^{N/k}\displaystyle\sum_{j=1}^{M/k}[d|i][d|j]\)
那就是\(\displaystyle\sum_{k\in {prime}}^{max(N,m)}\displaystyle\sum_{d}^{\lfloor\frac{N}{k}\rfloor}\mu(d) \lfloor\frac{N}{kd}\rfloor\lfloor\frac{M}{kd}\rfloor\)
然后整除分块，就是\(O(n/ ln\ n)\)就是质数的数量。
[HAOI2011] Problem b
题目描述
对于给出的 \(n\) 个询问，每次求有多少个数对 \((x,y)\)，满足 \(a \le x \le b\)，\(c \le y \le d\)，且 \(\gcd(x,y) = k\)，\(\gcd(x,y)\) 函数为 \(x\) 和 \(y\) 的最大公约数。
输入格式
第一行一个整数 \(n\)，接下来 \(n\) 行每行五个整数，分别表示 \(a,b,c,d,k\)。
输出格式
共 \(n\) 行，每行一个整数表示满足要求的数对 \((x,y)\) 的个数。
样例 #1
样例输入 #1
2
2 5 1 5 1
1 5 1 5 2
样例输出 #1
14
3
提示
对于 \(100\%\) 的数据满足：\(1 \le n,k \le 5 \times 10^4\)，\(1 \le a \le b \le 5 \times 10^4\)，\(1 \le c \le d \le 5 \times 10^4\)。
其实可以拆分成4个询问然后合并成答案，这样整除分块好算。
我们只要能够在合理的时间内求出\(\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{m}[gcd=k]\)就好了。而这个是板子。哦，这个是往上数的前两题。