2018.6.7清北学堂学习笔记

清北学堂 数论

Day2

---

上午

数论

数论是纯粹数学的分支之一,主要研究证整数的性质
初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说，初等数论的研究手段局限在整除性质上。
初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律、商高定理、佩尔方程的连分数求解法等等。
应用：密码学，hash算法等。

某些著名猜想
哥德巴赫猜想：是否每个大于2的偶数都可写成两个质数之和？
孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数
是否存在无穷多的梅森素数？
费马猜想（费马大定理）。
黎曼猜想

1.整除

• 对于整数$n,m$，如果$m\neq 0$且存在整数$k$，使得$km=n$，我们就称$m$整除$n$（或者$n$被$m$整除），$m$是$n$的约数，$n$是$m$的倍数。（不同的书上定义略有不同）
• 摘自《具体数学》（比值$n/m$是一个整数）

这个性质奠定了整个数论的基础，所以赋予它一个特殊记号会更方便，记为$m\mid n$。
整除的性质:
自反性：$a\mid a\ (a \neq 0)$
对称性：若$a\mid b, b\mid a$，则$a=\pm b$
传递性：如果$a\mid b$，$b\mid c$，那么$a\mid c$。
如果$bc\mid a$，那么$b\mid a$，$c\mid a$。
如果$b\mid a$，$c\mid a$，且$\gcd(b,c)=1$，那么$bc\mid a$。
如果$b\mid a$，且$d\mid c$，那么$bd\mid ac$。
设$b \neq 0$，如果$a|b$，则$|a| \le |b|$
$b\mid a \iff bm\mid am$（m是非零整数）。
$a\mid b$且$a\mid c$ $\iff$ 对任意两个整数$x,y$都有$a\ \mid \ bx+cy$。

---

传递性证明:
因为$b=ka,c=mb(k,m\in \mathbb{Z})$，所以$c=mka$。

---

$a\mid b$且$a\mid c$ $\iff$ 对任意两个整数$x,y$都有$a\ \mid \ bx+cy$
证明:
左边推出右边：
设$b=ka,c=la$，对于任意两个整数$x,y$都有$bx=kxa,cy=lya$，相加得：$bx+cy=(kx+ly)a$，故$a\ \mid \ bx+cy$
右边推出左边：
因为对任意两个整数$x,y$都有$bx+cy=ka$，
当$x=1,y=0$时，$b=ka$，故$a\mid b$。
当$x=0,y=1$时，$c=ka$，故$a\mid c$。

---

2.素数
定义：一个大于$1$的正整数，除了$1$和它自身外，不能被其他正整数整除的数叫做素数；否则称为合数。
素数有无限多个
证明(反证法):
假设有有限多个
那么记最大的素数$p_n$,假定$X=p_1 \times p_2 \times ... \times p_n$
那么$X+1$一定没有约数,所以它也是一个素数,且$X+1>p_n$,假设不成立
所以素数有无限多个

素数定理:

• 当$x$很大时，小于$x$的素数的个数近似等于$x/\ln(x)$。

---

算数基本定理

• 任何一个大于$1$的正整数$n$，都可以唯一分解成有限个素数的乘积。
  $$n = p_1p_2\cdots p_m = \prod_{k=1}^m p_k,\ p_1\leq \cdots \leq p_m.$$
• 也可以写成$n=p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}$

---

3.素数判定
给一个正整数 $n$，如何判定它是否为素数？

试除法！
解法0：枚举从 $2$ 到 $n - 1$ 的所有正整数，检查整除性，时间复杂度 $O(n)$。

---

解法1：枚举从 $2$ 到 $\sqrt{n}$ 的所有正整数，检查整除性，时间复杂度 $O(\sqrt{n})$
假设一个数能整除$n$，即$a \mid n$，那么$n/a$也必定能整除$n$，不妨设$a \le n/a$（否则可令$a = n/a$），则有$a^2 \le n$，即$a \le \sqrt{n}$

---

如果 $n$ 是合数，那么它必然有一个小于等于$\sqrt{n}$的素因子。
解法2：枚举从 $2$ 到 $\sqrt{n}$ 的所有素因子，检查整除性，单次时间复杂度 $O(\sqrt{n}/\ln(n))$

---

解法3：Miller-Rabin素性测试。

---

质因数分解
利用性质：如果 $n$ 是合数，那么它必然有一个小于等于$\sqrt{n}$的素因子
从 $2$ 到 $\sqrt{n}$ 枚举试除，对于一个因子不断除直到除净
最后可能会留有一个大的素因子。

---

4.因子
朴素的求因子的方法为枚举$[1, n]$的数进行整除判定，复杂度为$O(n)$
加入一个优化，如果$m$为$n$的因子，那么必然$n/m$也为$n$的因子，不妨设$m \le n/m$，则有$m \le \sqrt{n}$，所以只要从$[1,\sqrt{n}]$枚举即可
注意特判$x^2=n$（不要重复计算），复杂度$O(\sqrt{n})$

for(int i=1;i*i<=n;++i)
    if(n%i==0)
    {
        d[++dsz]=i;
        if(i*i<n)d[++dsz]=n/i;
    }

$n=p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}$
由乘法计数原理得，约数个数为$(r_1 + 1) \cdot (r_2 + 1) \cdots (r_k + 1)$

---

5.筛素数
给一个正整数 $n$，求出不超过 $n$ 的所有素数。

埃拉托斯特尼筛法
逐次枚举 $2$ 到 $n$，设当前枚举到 $x$，如果$x$没有被标记过，那么$x$是素数，并将$x$的倍数标记为“非素数”。

朴素版写法
bool not_prime[];
not_prime[1]=true;
for(int i=2;i<=n;++i)
    for(int j=i+i;j<=n;j+=i)
        not_prime[j]=true;

复杂度为$O(n(\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n})$
根据调和级数,大概是$O(n\log n)$

bool not_prime[];
not_prime[1]=true;
for(int i=2;i<=n;++i)
    if(!not_prime[i])
        for(int j=i+i;j<=n;j+=i)
            not_prime[j]=true;

复杂度$O(n\log\log n)$

---

线性筛
逐次枚举 $2$ 到 $n$，并且记录下当前找到的所有素数。
然后每处理到一个数$x$，从小到大枚举所有当前找到的素数，将其与$x$的乘积剔除。直到$x$被当前枚举的素数整除为止。

bool not_prime[];
int prime[],psz;
not_prime[1]=true;
for(int i=2;i<=n;++i)
    if(!not_prime[i])prime[++psz]=i;
    for(int j=1;j<=psz;++j)
    {
        if(i*prime[j]>n)break;
        not_prime[i*prime[j]]=true;
        if(i%prime[j]==0)break;
    }

第10行那句话是保证线性复杂度的关键
例:
30
6*5筛掉一次
10*3筛掉一次
15*2筛掉一次
会被重复筛除
加上这句话之后
30只会被15*2筛掉
可以保证每个数都被它最小的质因子筛除了,故算法复杂度$O(n))$

例题：
给定$n(n < 10000)$个数，范围为$[1, 2^{32})$，判定它们是素数还是合数。

解：
首先1不是素数，如果$n>1$，则枚举$[1,\sqrt{x}]$范围内的素数进行试除
$[1,\sqrt{M}]$范围内的素数可以通过筛法预先筛出来。

---

区间筛
题目:给定l,r$(1 \le l \le r\le 10^9,r-l < 10^5$,求[l,r]范围内的素数
解法:枚举$[1,\sqrt r]范围内的素数来筛$
$[1,\sqrt r]$范围内的素数可以通过筛法预先筛出来

//前面有个线性筛
for(int i=1;i<=psz;++i)
{
    int p=prime[i];
    for(int j=(l-1)/p+1;j<=r/p;++j)
        not_prime[j*p-l]=true;//-l是因为l和r的取值太大,但是l~r比较小
}

复杂度$O((r-l)\log n)$
也可以枚举[m,n]上面每个数,用Miller-Rabin算法判定,但是没有充分利用题目性质

---

6.mod运算
定义来自于带余除法

除法定理

• 如果$n,m$是两个整数，$m\neq 0$，存在唯一一对整数$q$和$r$，满足$n = qm + r$且$0\leq r < |m|$

对任意整数$n$和任意整数$n$，称$q = \lfloor n / m \rfloor$为除法的商，值$r = n \bmod m$为除法的余数[1]
也就是$n = m \lfloor n / m \rfloor + n \bmod m, m \neq 0$
这就将mod定义成为一个二元运算，该定义当$n,m$是实数时也有意义，不过在数论中我们通常只对整数用此定义。
当$n$或$m$是负数时，计算机语言用的是另一种定义。

---

最大公约数
定义:

• 两个整数$m$和$n$的最大公约数是能整除它们两者的最大整数。记为$\gcd(m,n)$或$(m,n)$

int gcd(int a,int b)
{return b?gcd(b,a%b):a;}

对于$0\leq m < n$计算$\gcd(n, m)$，欧几里得算法用到递归式
$\gcd(0, n) = n;$
$\gcd(m, n) = \gcd(n \bmod m, m), m > 0$

求证:对任意非负整数$a$和正整数$b$，$\gcd(a,b) = \gcd(b,a \bmod b)$。
证明:
只需要证明上面两者能相互整除。
设$\gcd(a,b)=d$所以$d \mid a$且$d \mid b$
由带余除法可以得出：$a \bmod b = a - qb$，其中$q = \lfloor a / b \rfloor$
所以$a \bmod b$是a和b的一个线性组合，所以$d \mid a \bmod b$
又因为$d \mid b$
所以$d \mid \gcd(b,a \bmod b)$，即$\gcd(a,b) \mid \gcd(b,a \bmod b)$。

证明$\gcd(b,a \bmod b) \mid \gcd(a,b)$和上述过程几乎一样。

---

裴蜀定理

对任何$a,b \in Z$和它们的最大公约数$d$，关于未知数$x$和$y$的线性不定方程（称为裴蜀等式）：$ax+by=c$有整数解$(x,y)$当且仅当$d \mid c$，可知有无穷多解。特别地，一定存在整数$x,y$，使$ax+by=d$成立。

• 引理:
  $a$与$b$的线性组合集中最小的正元素是$\gcd(a,b)$

引理的证明:
设$s$是$a$与$b$的线性组合集中最小的正元素，对于某个$x,y \in Z$，有$s=ax+by$
设$q = \lfloor a/s \rfloor$，则有
$r = a\;mod\;s = a - qs = a - q(ax+by) = a(1-qx)+b(-qy)$
因此$r$也是$a$与$b$的一个线性组合
由于$s$是这个线性集合中的最小正整数，又$0 \le r < s$，可得$r=0$
因此有$s \mid a$，同理有$s \mid b$，因此$s$是$a$与$b$的公约数，所以有$d \ge s$
其实用exgcd就能得出存在等于$d$的线性组合。
证毕

• 充分性：已知$ax+by=d$一定有整数解，设其解为$(x_0,y_0)$
  已知$d \mid c$，则存在$k \in Z$，使得$c = kd = k(ax+by) = a(kx) + b(ky)$，即解为$(kx_0,ky_0)$
• 必要性：$d \mid a$，$d \mid b$，$d \mid ax+by$，所以$d \mid c$
  必要性的另一种表达
  设$d = \gcd(a,b)$
  因$ax_1+by_1=c$，$x_1,y_1 \in Z$，有$d \mid a$，$d \mid b$，$d \mid (ax_1,by_1)$，即$d \mid c$

裴蜀定理可以从二元拓展到多元

• 推论1
  对任意整数$a$与$b$，如果$d \mid a$且$d \mid b$，则$d \mid \gcd(a,b)$
• 推论2
  $a$与$b$互质的充要条件是，存在整数$x,y$，使得$ax + by = 1$
• 推论3
  若$a \mid bc$，且$(a,b)=1$，则$a\mid c$
  推论3证明:
  存在整数$m,n$，使得$am + bn = 1$
  于是$acm+bcn=c$
  又因为$a\mid ac,a\mid bc$
  所以$a\mid acm+bcn$，即$a\mid c$
• 推论4
  若质数$p \mid ab$，则$p\mid a$或$p\mid b$
  推论4证明:只有两种情况$(a,p)=p$或$(a,p)=1$，第一种就是$p\mid a$，第二种由推论3的性质得$p\mid b$

素数的推论4这条性质可以推广到一般情形，若$p\mid a_1a_2\cdots a_k$，则存在$a_i$使得$p\mid a_i$

---

7.素数、算数基本定理

任何一个大于$1$的正整数数$n$，都可以唯一分解成有限个素数的乘积

$$n=p_1 \times p_2 \times \cdots \times p_m = \prod_{k=1}^m p_k,p_1 \le p_2 \le \cdots \le p_m$$
也称唯一分解定理

存在性证明:
如果$n>1$不是素数，那么他就有一个因子$n1$，使得$1<n_1<n$，这样我们就能写成$n=n_1 n_2$，同时（根据归纳法）我们知道$n_1$和$n_2$可以写成素数的乘积

唯一性证明:
反证法
假设$n$有两种方法分解，$n = p_1p_2 \cdots p_m = q_1q_2 \cdots q_s$
用刚刚得出的引理：若$p\mid a_1a_2\cdots a_k$，则存在$a_i$使得$p\mid a_i$。因为$p_1 \mid q_1q_2 \cdots q_s$所以存在$q_i$使得$p_1 \mid q_i$，又因为$q_i$也是质数，所以$p_1=q_i$，同时除掉之后由归纳法即可得证

由算数基本定理$n=p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}$
两个数相乘就等价于指数表示相加。
$k=mn \iff k_p = m_p + n_p$，对所有$p$
这就蕴含
$m \mid n \iff m_p \le n_p$，对所有$p$
由此可以立即推出
$k = \gcd(m, n) \iff k_p = \min(m_p, n_p)$，对所有$p$
$k = \text{lcm}(m, n) \iff k_p = \max(m_p, n_p)$，对所有$p$

由此还可得一个小结论$n \cdot m = \gcd(m, n) \cdot \text{lcm}(m, n)$

例题：hdu4497 GCD and LCM
三个未知数$x, y, z$，它们的gcd为$G$，lcm为$L$，$G$和$L$已知，求$(x, y, z)$三元组的个数
解法：
对于每个素因子单独处理
假设素因子为$p$ ，$L$分解式中$p$的指数为$l$，$G$分解式中$p$的指数为$g$，那么显然$l < g$时不可能存在满足条件的三元组，所以只需要讨论$l \ge g$的情况，对于单个$p$因子，问题转化成了求三个数$x_1, y_1, z_1$，满足$\min(x_1, y_1, z_1) = g$且$\max(x_1, y_1, z_1) = g$，这是一个排列组合问题，三元组$x_1, y_1, z_1$的种类数当$l = g$时只有1中，否则答案就是 $6(l - g)$
最后根据乘法原理将每个素因子对应的种类数相乘即为最后的答案了

---

8.扩展欧几里得
求解不定方程$ax+by = \gcd(a, b)$(假设$a\geq b$)
当$b=0$时有$\gcd(a,b)=a$,此时$x=1,y=0$
当$b$不为$0$时,根据GCD递归定理$\gcd(a,b) = \gcd(b,a \bmod b)$
可得$ax+by = \gcd(a, b) = \gcd(b,a \bmod b) = bx' + (a \bmod b)y'$
即$ax+by = bx' + (a\bmod b)y' = bx' + (a-b*\lfloor a/b \rfloor)y'$
移项得$ax+by = bx' + (a\bmod b)y' = ay'+b(x'- \lfloor a/b\rfloor y')$
所以$x=y',y=x'- \lfloor a/b\rfloor y'$
设 $(x_0, y_0)$ 是不定方程 $ax + by = m$ 的一组解， $(a, b) = g$，那么全部解为$(x_0 + (b/g)t, y_0 - (a/g)t)$，其中 $t$ 为所有整数

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

例题:
2012NOIP同余方程
已知$ax \equiv 1\pmod b$,且a,b互质,求x
做法:转化为$ax+by=1$,代进exgcd直接求即可,y没用,x即为答案

poj1061青蛙的约会
两只青蛙同向跳跃,A的出发点是x,B的出发点是y,它们在一个首尾相接的数轴上
A一次跳m米,B一次跳n米,数轴总长度为l
问它们至少跳了几次之后可以相遇
解:
求解a：

$$x+am\equiv y+an\pmod L$$
它就等于
$$a(m-n)\equiv y-x\pmod L$$
把模去掉，就等于
$$a(m-n)+Lk=y-x$$
然后，用exgcd求
$$a(m-n)+Lk=gcd(m-n,L)$$

NOI2002荒岛野人
一个岛是环状的，环上排列有 $M$ 个洞穴，顺时针编号为1到 $M$ ，有 $N$ (不超过 $15$ ) 个野人，第 $i$ 个野人一开始住在洞穴 $C_i$ 中，每一年要顺时针迁移 $P_i$ 个洞穴，走 $L_i$ 年后就会死去。求满足在野人有生之年都不存在两个野人同住一个洞穴的情况下，最少的洞穴总数。保证 $M$ 不超过 $10^6$

解法：
答案不满足单调性，不能二分。我们只能从小到大枚举洞穴数$M$，检查其是否能满足条件，和上一题类似

---

9.mod：同余关系
若两个整数$a,b$除以正整数$m$有相同的余数，那么称$a,b$对于模$m$同余，用式子表示为：
$a \equiv b \pmod m \iff a \bmod m = b \bmod m$
在不产生歧义的情况下，可以省略$\pmod m$
我们可以用另一种方式来解读同余式：$a-b=mk$，$k$是整数，即$m \mid a-b$。
同余是一个等价关系，它满足自反律$a \equiv a$，对称律$a \equiv b$，传递律$a \equiv b \equiv c \Rightarrow a \equiv c$，这些都很容易证明。
此外，它还满足可加减性：若$a \equiv b$ 且 $c \equiv d$，那么$a \pm c \equiv b \pm d$。 可乘性：若$a \equiv b$ 且 $c \equiv d$，那么$ac \equiv bd$。
我们对方程所习惯做的大多数运算对同余式都可以运用。但要注意，除法运算是有条件的

10.逆元
*定义:
设正整数模 $m$，对于任意正整数 $a$ 满足 $(a, m) = 1$，存在 $b$ 满足
$ab \equiv 1 \pmod m$，称 $b$ 为模 $m$ 意义下 $a$ 的逆元。%且 $1 \le b \le m$

求逆元只需要用扩展欧几里得解一个线性同余方程$ab+mt=1$即可，还可以用费马小定理或欧拉定理来求。
而$a$有逆元的充要条件是$(a,m)=1$（方程有解）

O(n)预处理求逆元1~n的逆元

q[1]=1;
for(int i=2;i<=n;++i)
    q[i]=q[i-1]*i%mod;
p[n]=ksm(q[n],mod-2);
for(int i=n;i>1;--i)
    p[i-1]=p[i]*i%mod;

另一种解法:

$$p=k*i+r$$
$$k*i+r\equiv0(\mod p)$$
$$k*i*i^{-1}*r^{-1} + r*i^{-1}*r^{-1}\equiv0(\mod p)$$
$$k*r^{-1}+i^{-1}\equiv 0 (\mod p)$$
$$i^{-1}\equiv -k*r^{-1}(\mod p)$$

$$a^i \equiv a^j(\mod b) \iff i \equiv j(\mod b)$$

11.剩余系、完全剩余系和简单剩余系

• 定义1——剩余类：
  把关于模$m$同余的数归于一类，每类称为一个模$m$的剩余类。即由关于模$m$同余的数组成的集合，每一个集合叫做关于模$m$的一个剩余类(又叫同余类)。共有$m$个剩余类。
  设$K_r$是余数为$r$的剩余类，
  则$K_r = \{ qm+r \mid q \in \mathbb{Z} \} = \{ a \mid a \in \mathbb{Z}, a \equiv r \pmod m \}$

• 定义2——完全剩余系：
  设$K_0,K_1 \cdots K_{m-1}$是模$m$的$m$个剩余类，从$K_r$中各取一数 $a_r$ 作为代表，则这样的$m$个数 $a_0,a_1 \cdots a_{m-1}$ 称为模$m$的一个完全剩余系，简称$m$的完系。例如最小非负完全剩余系：$0,1,2, \cdots ,m-1$

• $m$个整数构成模$m$的一完全剩余系 $\iff$ 两两模$m$不同余

• 设$(a,m)=1,b \in \mathbb{Z}$，若$x_1,x_2, \cdots ,x_m$是模$m$的一个完全剩余系，则$ax_1+b,ax_2+b, \cdots ,ax_m+b$也是模$m$的一个完全剩余系；特别地，$m$个连续的整数构成模$m$的一个完系。

• 定义3——简化剩余系
  也称既约剩余系或缩系，是模n的完全剩余系的一个子集，其中每个元素与n互素

---

下午

12.费马小定理
设$p$是一个素数，$a$ 是一个整数且不是 $p$ 的倍数，那么

$$a^{p-1} \equiv 1 \pmod p$$
注意到若有 $i \not\equiv j \pmod p$，那么有 $i \times a \not\equiv j \times a \pmod p$。
所以$1 \times a, 2 \times a, \cdots, (p - 1) \times a$构成模$p$的一个完全剩余系。
由完全剩余系的性质，
$1 \times 2 \times 3 \times \cdots \times (p - 1) \equiv (1 \times a) \times (2 \times a) \times \cdots \times ((p - 1) \times a) \pmod p$
即$(p-1)! \equiv (p-1)! \times a^{p-1} \pmod p$
又 $\gcd((p-1)!, p) = 1$，故$a^{p-1} \equiv 1 \pmod p$

---

13.素性测试
很遗憾，费马小定理的逆定理是不成立的。
对 $a = 2$，满足 $2^{n-1} \bmod n = 1$ 的非素数 $n$ 是存在的，比如 $n = 341 = 11 \times 31$

对于整数 $a$，称满足 $a^{n-1} \bmod n = 1$ 的合数为以 $a$ 为底的 伪素数

经测试，前 10 亿的自然数中，同时以 2 和 3 为底的伪素数有 1272 个。
我们用费马小定理验证素数的话，出错的概率大概只有 0.000025。可以制作一张伪素数表

如果我们随机选取若干个小于待测整数的正整数作为底 $a$，然后用费马小定理来测试,存在无穷多个被称为Carmichael数的整数：对于任意与其互素的整数$a$算法的计算结果都是1
最小的五个Carmichael数是561、1105、1729、2465和2801。

---

MillerRabin素性测试

费马小定理的逆命题不成立，所以只能使用逆否命题
二次探测定理

$$a^{n-1} \equiv 1 (\mod n)$$
$$a^{(n-1)/2} ?\equiv -1 (\mod n)$$
$$a^{(n-1)/4} ?\equiv 1 (\mod n)$$
$$a^{d\times 2^{i+1}} \equiv 1 (\mod n)$$
$$a^{d\times 2^{i+2}} \equiv 1 (\mod n)$$

若$p$是素数，$x$是一个正整数，且 $x^2 \bmod p = 1$，那么 $x \equiv \pm 1 \pmod p$。
由$x^2 \bmod p = 1$即 $p \mid x^2 - 1$ 即 $p \mid (x + 1)(x - 1)$，由 $p$ 是素数易证。
设待测数为 $n$，取一个比 $n$ 小的正整数 $a$，设 $n - 1 = d \times 2^r$，若 $n$ 是素数，则要么$a^d \bmod n = 1$，要么存在一个 $i$，满足 $0 \le i < r$ 且 $a^{d \times 2^i} \bmod n = -1$。
随机选取 $k$ 个小于待测整数 $n$ 的正整数作为底 $a$，用上面的结论来测试
时间复杂度 $O(k \log^2 n)$

#include <ctime>
#include <cstdio>
#include <algorithm>
typedef long long ll;
const int C=240,Time=10;
ll ans;
int T;
ll mult(ll x,ll y,ll mod)
{
    ll ret=0;
    for(;y;y>>=1,x=(x+x)%mod)
        if(y&1)
            ret=(ret+x)%mod;
    return ret;
}
ll ksm(ll x,ll y,ll mod)
{
    ll ret=1;x%=mod;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)
            ret=ret*x%mod;
    return ret;
}
ll gcd(ll a,ll b)
{
    if(!a)return 1;
    if(a<0)return gcd(-a,b);
    return b?gcd(b,a%b):a;
}
bool Witness(ll a,ll n)
{//二次探测定理
    ll t=0,u=n-1;
    while(!(u&1))++t,u>>=1;
    ll x0=ksm(a,u,n);
    if(x0==1)return 0;
    for(int i=0;i<t;++i)
    {
        if(x0==n-1)return 0;
        x0=mult(x0,y0,n);
    }
    return 1;
}
bool Miller_Rabin(ll n,ll t)
{
    if(n==2)return 1;
    if(!(n&1))return 0;
    srand(time(0));
    for(int i=0;i<t;++i)
    {
        ll a=rand()%(n-1)+1;
        if(Witness(a,n))return 0;
    }
    return 1;
}
/*//后面的内容是Pollard_Rho分解大数质因子
ll Pollard_Rho(ll n,ll c)
{
    ll x=rand()%n,y=x,k=2;
    for(int i=2;;++i)
    {
        x=(mult(x,x,n)+c)%n;
        ll d=gcd(y-x,n);
        if(d!=-1&&d!=n)return d;
        if(x==y)return n;
        if(i==k)y=k,k<<=1;
    }
}
void get_small(ll n,ll c)
{
    if(n==1)return ;
    if(Miller_Rabin(n,Time))
    {
        ans=min(n,ans);
        return ;
    }
    ll p=n;
    while(p>=n)p=Pollard_Rho(p,c--);
    get_small(p,c);
    get_small(n/p,c);
}
*/
int main()
{
    srand(time(0));
    scanf("%d",&T);//多组数据
    while(T--)
    {
        ll n;
        scanf("%lld",&n);
        if(Miller_Rabin(n,Time))
            printf("Maybe a prime\n");
        else
        {
            printf("Not a prime\n");
            /*
            ans=n,getsmall(n,C);
            printf("%lld",ans);
            */
        }
    }
    return 0;
}
*/

---

中国剩余定理
在《孙子算经》中有这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
《孙子歌诀》：三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。
例：求解一元线性同余方程组:

$$\begin{align*} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ &\vdots \\ x &\equiv a_n \pmod {m_n} \end{align*}$$
当$m_i$两两互素的时候，是经典的中国剩余定理，百度百科有详细的介绍
$$\begin{align*} x &\equiv a_1 \pmod {m_1} \\ x &\equiv a_2 \pmod {m_2} \\ \end{align*}$$
它等价于
$$\begin{align*} x=a_1+k_1m_1 \\ x=a_2+k_2m_2\\ \end{align*}$$
两个方程联立
$$k_1m_1-k_2m_2=a_2-a_1$$
根据裴蜀定理,我们可以知道如果$\gcd(m1,m2)\mid(a2-a1)$，那么这个方程就有整数解，否则它就不存在整数解

$$M_i = \prod_{j,j\neq i}m_i$$
$$ans = \sum_{i}a_iM_it_i$$

对于

$$\begin{align*} k_1=\frac{m_1}{g}t+k'_1\\ k_2=\frac{m_2}{g}t+k'_2\\ \end{align*}$$
其中g为gcd(m1,m2)
往回代入可得
$$\begin{align*} x&=a_1+k_1m_1\\ &=x_0+\frac{m_1m_2}{g}t\\ &=x_0+lcm(m_1,m_2)t\\ \end{align*}$$
这个解实际上等价于下面这个同余方程
$$x\equiv x_0 \pmod{lcm(m_1,m_2)}$$

例题：
求

$$\sum_{i=1}^n{\lfloor \frac{n}{i} \rfloor}$$
其中$(1 \le n \le 10^9)$

这是个非常经典的问题
其非常经典的思路:
对$n/i$取余,一共约有$2\sqrt n$个结果
对于$i \le \sqrt n$,$n/i$有$\sqrt n$种结果
对于$\sqrt n \lt i \le n,n/i$的范围是$1\le n/i \le \sqrt n$,至多有$\sqrt n$种结果

其非常经典的写法:

for(int i=1,j;i<=n;i=j+1)
{
    j=n/(n/i);
    ans+=(j-i+1)*(n/i);
}

例题2：余数之和
输入$n,k$,计算$\sum_{i=1}^n k \mod i$的结果

解法：
和上一个问题类似,商至多有$2\sqrt k$种
又注意到对于商相同，余数是一个等差数列
如果除数的范围是[l,r]，商为k，那么对答案的贡献是$(r-l+1)*k-a(l+r)(r-l+1)/2$

例题3:模积和
输入n,m,计算

$$\sum_{i=1}^n \sum_{j=1 \wedge j\ne i}^{m}(n \bmod i)(m \bmod j)$$

解法：
如果没有$i\ne j$这个条件,那么后面可以用分配率拆成两部分,然后乘起来
$\sum_{i=1}^n \mod i$是很容易在$O(\sqrt n)$的时间内计算的
现在要求$i\ne j$，那么容易想到先算出全部,然后减去$i=j$的部分
再考虑对于$n/i$和$m/j$结果都相同的一组，$n \mod i,m\mod j$有什么相纸
容易发现后面两个均为等差数列,用分配率和前n个自然数和,平方和的公式就可以在$O(1)$的时间内计算了。
总时间复杂度$O(\sqrt n+\sqrt m)$

具体化简过程:

$$\begin{align*} &\sum_{i=1}^n \sum_{j=1 \wedge j\ne i}^{m}(n \bmod i)(m \bmod j)\\ &=\sum_{i=1}^n\sum_{j=1}^m(n-\lfloor\frac{n}{i}\rfloor i)(m-\lfloor \frac{m}{j}\rfloor j)-\sum_{i=1}^{\min(n,m)}(n-\lfloor\frac{n}{i}\rfloor i)(m-\lfloor \frac{m}{i}\rfloor i)\\ &=\bigg(\sum_{i=1}^n(n-\lfloor\frac{n}{i}\rfloor i)\bigg)\bigg(\sum_{j=1}^m(m-\lfloor\frac{m}{j}\rfloor j)\bigg)-\sum_{i=1}^{\min(n,m)}\Big(nm+\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2-(m\lfloor\frac{n}{i}\rfloor+n\lfloor\frac{m}{i}\rfloor)i\Big)\\ \end{align*}$$

---

14.数论函数

数论函数是定义在整数集合商的函数
一些常见的数论函数:
* $\sigma(n)=\sum_{d\mid n}d$,表示正整数n的正因子之和
* $d(n)=\sum_{d\mid n}1$,表示正整数n的正因子个数
* $\varphi(n)$表示[1,n]中与n互素的整数个数,称作欧拉函数

数论函数f叫做是积性函数
对于gcd(n,m)==1,若f(n*m)=f(n)*f(m)那么称函数f为积性函数
若对于任意n,m都有f(n*m)=f(n)*f(m),那么称函数f为完全积性函数

---

欧拉函数
考虑如何计算$\varphi(n)$
$\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1}$
$\varphi(n)$是积性函数，但不是完全积性函数
一个有趣的推论:$\sum_{d|n}\varphi(d)=n$
考虑分母为n的真分数,和他们化成最简分数，可以说明这个结论

欧拉定理

• 设n为正整数,a是与n互素的整数,则$a^{\varphi(n)}\equiv 1\pmod n$

欧拉定理的证明与费马小定理类似

线性欧拉筛

bool not_prime[];
int prime[],psz;
not_prime[1]=true;
phi[1]=1;
for(int i=2;i<=n;++i)
    if(!not_prime[i])
    {
        prime[++psz]=i;
        phi[i]=i-1;
    }
    for(int k,j=1;j<=psz;++j)
    {
        k=i*prime[j];
        if(k>n)break;
        not_prime[i*prime[j]]=true;
        if(i%prime[j]==0)
            phi[k]=prime[j]*phi[i];
        else                phi[k]=phi[i]*(prime[j]-1);
    }

---

莫比乌斯函数$\mu$
如下定义莫比乌斯函数$\mu$

$$\mu(n)=\begin{cases} 1,n=1\\ (-1)^k,n=p_1p_2 \cdots p_k,p_i,(\forall i \ne j, p_i \ne p_j)\\ 0,otherwise\\ \end{cases}$$

线性莫比乌斯函数筛

bool not_prime[];
int prime[],psz;
not_prime[1]=true;
phi[1]=mu[1]=1;
for(int i=2;i<=n;++i)
{
    if(!not_prime[i])
    {
        prime[++psz]=i;
        phi[i]=i-1;
        mu[i]=-1;
    }
    for(int k,j=1;j<=psz;++j)
    {
        k=i*prime[j];
        if(k>n)break;
        not_prime[k]=true;
        if(i%prime[j]==0)
            mu[k]=0;
        else    mu[k]=-mu[i];
    }
}

$$\sum_{d\mid n}\mu(d)=[n=1]$$
其中$[n=1]$表示:当$n=1$时值为1,否则为0
那么$n=1$时显然
$n\gt 1$,设$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$
显然d的每个质因子的指数为1才有贡献,否则$\mu(d)=(-1)^r$,这样的d有C_m^r个
所以 $$\sum_{d\mid n}\mu(d)=\sum_{r=0}^m(-1)^rC_m^r$$
已知有二项式定理(看百度百科好像是杨辉三角),则
$$\sum_{r=0}^m(-1)^rC_m^r=\sum_{r=0}^mC_m^r(-1)^r1^{m-r}=(-1+1)^m=0$$

---

莫比乌斯反演
有两种写法
1.

$$F(n)=\sum_{d\mid n}f(d) \iff f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d})$$
2. $$F(n)=\sum_{n\mid d}f(d)\iff f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$$

对于第一个写法的证明：

$$\begin{align*} &\sum_{d\mid n}\mu(d)F(\frac{n}{d})\\ =&\sum_{d\mid n}\mu(d)\sum_{i\mid\frac{n}{d}}f(i)\\ =&\sum_{i\mid n}f(i)\sum_{d\mid\frac{n}{i}}\mu(d)\\ =&f(n) \end{align*}$$

例题链接

T1
$\gcd(x,y)=1,0\le x,y\le n$的对数
解法
求phi的前缀和
T2
$\gcd(x,y)$是质数,$0\le x,y\le n$的对数
SDOI2008仪仗队

前两题数据范围5w

T3
$\gcd(i,j,k)=1,0\le i,j,k \le n$的个数
解法
$g(x): x \mid gcd(i,j,k)$的组数
$f(x): x=gcd(i,j,k)的组数$

$$g(x) = \sum_{x\mid n}f(n)$$
$$g(x)=\lfloor n/x \rfloor ^ 3$$

T4
$\gcd(x,y)=d,1\le x\le a,1\le y\le b$的个数，多组数据
解法

$$g(x)=\lfloor a/x \rfloor \lfloor b/x \rfloor$$
由考虑到多组数据,使用整除分块
$$f(d)=\sum_{d\mid x}\mu(x/d)g(x)$$
$$f(d)=\sum_{d\mid x}\mu(x/d) \lfloor a/dx \rfloor \lfloor b/dx \rfloor$$
$$\lfloor a/dx \rfloor=\lfloor\lfloor a/d \rfloor/x\rfloor$$
数据组数和数据范围都是5w

T5
$\gcd(x,y)=k,a\le x\le b,c\le y\le d$的个数，多组数据

$$f(d)=\sum_{1\mid x}\mu(x) \lfloor \lfloor a/d \rfloor /x \rfloor \lfloor \lfloor b/d \rfloor x \rfloor$$