Div1. 数论有关定理#

算术基本定理：每一个合数都可以被分解为有限个质数的乘积。即对于任意合数$n$，都存在：

$n=p_{1}^{c_1}p_{2}^{c_2}p_{3}^{c_3}...p_{k}^{c_k}$，其中$p$为质数。

推论一：正整数$n$的正因数集合为：

$\{n=p_{1}^{b_1}p_{2}^{b_2}p_{3}^{b_3}...p_{i}^{b_i} \mid 1 \leq b_i \leq c_i, 1 \leq i \leq k\}$

推论二：正整数$n$的正因数个数为：$\tau (n)= (c_1+1) \cdot(c_2+1) \cdot (c_3+1) ... (c_k+1) =\prod_{i=1}^{k}\left( c_i+1\right) \\$

推论三：正整数$n$的所有正因数之和为

$\sigma(n)=(p_1+p_1^2+...+p_1^{c_1}+1)\times (p_2+p_2^2+...+p_2^{c_2}+1)\times...\times (p_k+p_k^2+...+p_k^{c_k}+1)=\prod_{i=1}^{k}\frac{p_k^{c_k+1}}{p_k-1}$

质数分布定理：区间$[1,N]$中，当$N\to \infty$时，质数个数$\pi (x)\approx \frac{n}{\ln n}$。

费马小定理： 若$p$是一个质数，则$a^p\equiv a\bmod p$（$\equiv$为同余符号）。

欧拉定理（费马小定理扩展）： 若$a\perp n$（$a$与$n$互质），则有$a^{\varphi{(n)}} \equiv 1 \bmod n$，其中$\varphi(n)$为欧拉函数。

Div2. 同余#

同余，顾名思义，两个数分别除以一个正整数$m$后得到相同的余数。即$a\bmod m=b\bmod m$。但是它的定义给出了这样一句话：“对于正整数$a$和$b$，若$(a-b)\mid m$（$a-b$能被$m$整除），则称$a$和$b$对模$m$同余，记作$a\equiv b\pmod m$”。当然以上两种说法是等价的。

同余具有以下三种基本性质：

1. 反身性：对于任何正整数$a$，$a\equiv a\pmod m$
2. 对称性：即对于$a\equiv b\;(\bmod m)$，有$b\equiv a\pmod m$
3. 传递性：若$a\equiv b\pmod m$，且$b\equiv c\pmod m$，有$a\equiv c\pmod m$

当然，它可以延申到计算机的模运算（毕竟出现了$\bmod$）。模运算有三种基本运算：

1. 加运算：$(a+b)\% m=(a\% m+b\% m)\% m$
2. 减运算：$(a-b)\%m=(a\%m-b\%m)\%m$
3. 乘运算：$(a\cdot b)\%m=((a\%m)*(b\%m))\%m$

还有两个推论：

1. 幂运算：$a^b\%p=((a\%p)^b)\%p$
2. 求和运算：$(\sum\limits_{x=1}^{n}x)\%p=(\sum\limits_{x=1}^{n}x\%p)\%p$

同余消去原则：

若同余号两端的项相等，且都与模$n$互质，则可以同时消去

举例：$a\cdot c\equiv b\cdot c \bmod n$，如果$gcd(c,n)=1$，则$a\cdot c\equiv b\cdot c\Rightarrow a\equiv b \bmod n$。

Div1.  质数判断#

试除法： 这是三种方法中，唯一一种能做到100%正确的质数判断方法。对于给定数$n$，遍历所有$[2,\sqrt n]$间的正整数$m$，若出现$m\mid n$则证明它不是质数，因为质数只能被1以及它本身整除。

1
bool isPrime(int n) {
2
  for (int i = 2; i * i <= n; i++) {
3
    if (n % i == 0) return false;
4
  }
5
  return true;
6
}

复杂度：$\mathcal O(\sqrt n)$

适用范围：普及、提高

试除法の大胜利！

费马素性检验： 是上述费马小定理的实际运用，它与常规算法思想有所不同：它主张在$[2,n-1]$中随机选取一个数$a$。若出现与费马小定理不符的情况，那么$n$一定为合数；若每次均符合定理，称为 费马伪素数 ，因为它很大概率是一个质数。

1
bool isPrime(int n) {
2
  if (n <= 2) return false;
3
  int k = 10;
4
  while (k--) {
5
    srand(time(0));
6
    int a = rand() % (n - 2) + 2;
7
    if (__gcd(a, n) != 1) return false;
8
    if (qpow(a, n - 1, n) != 1) return false;
9
  }
10
  return true;
11
}

复杂度：$\mathcal O(k\log n)$，其中$k$为随机数检验次数，$\log n$是因为使用了快速幂算法。

适用范围：提高T2及以下（慎用）

为什么用该方法判断的质数 大概率 是个质数呢？不妨测试一下561（3）、1105（5）、1729（7）（括号内为它的最小因子），你会发现函数的返回值均为true，即都为质数。可见这个算法不是100%正确的，这些“漏网之鱼”被称为“Carmichael数”。它们极其罕见，一亿范围内仅255个。也因如此，你可以通过打表特判的方式抠掉这些特例（你保证记得住就行）。2016年中国物流工人余建春给出了一个Carmichael数的判断准则，这个标准目前在国际上得到了广泛认同。

对于优化，你可以在函数起始点加入类似于if (n % 2 == 0 || n % 3 == 0) return false;的特判，进一步降低复杂度。

Miller-Rabin算法： 该算法同样无法保证结果100%准确，慎用！

MB算法实质上是对费马素性检验算法的效率和准确度优化。算法流程如下：

1. 将$n-1$分解为$2^s+d$的形式，其中$d$为奇数
2. 从$[2,n-2]$中选取整数$a$，称为“基数”
3. 计算$a^d \bmod n$的值，若结果为$1$或$n-1$，则可能为质数，继续检验
4. 若结果不等于$1$或$n-1$，计算$a^{2d} \bmod n$、$a^{4d} \bmod n$、$a^{6d} \bmod n$……$a^{2^{s-1}d} \bmod n$的值，若结果等于$n-1$，则可能为质数，继续检验
5. 若都不等于$1$，则$n$一定是合数。称为强费马证据。

当然，它同样有特例，称为强伪质数，如2047（23）、3277（29）、4033（39）等（括号内为它的最小因子）。

Div2.  质数筛#

常见的质数筛法有：试除法、埃氏筛、线性筛。

试除法：从质数定义出发，即存在一个正整数$N$，对于任意$[2,\sqrt N]$间的正整数$M$，总有$N\bmod M \neq 0$成立。代码实现只需枚举$[2, \sqrt N]$间所有正整数，并让$N$对其取余。若取模运算出现$0$则代表它不为质数，没有出现$0$则为质数。

1
bool isPrime(int n) {
2
  for (int i = 2; i * i <= n; i++) {
3
    if (n % i == 0) return false;
4
  }
5
  return true;
6
}

复杂度：$\mathcal O( \sqrt N )$

适用范围：普及T2及以下

这里所展示的试除法代码实际上经过一轮优化。若严格根据质数定义，第二行的循环上限应为$n-1$。考虑到如下性质：$\forall m\in [2,\sqrt N]$，若$m\mid N$，则一定有$\frac{N}{m}\mid N$。因此可以将循环上限压缩至$\sqrt N$。

埃氏筛：全称叫埃拉托斯特尼筛法，老哥生活在2200年前的古希腊，不借助望远镜就计算出了地球的周长（与真实值偏差仅0.96%）、同时他也是第一位根据经纬线绘制出世界地图的人、也是最先提出将地球根据南北回归线分为“五带”的大人物。他提出的筛法核心思想如下：

第一步：列出从2开始的一列连续数字；第二步：选出第一个质数（本例中为2），将该质数标记，将数列中它的的所有倍数划去；第三步：若数列中的末项小于它前一项的平方，则质数已全部筛出；否则返回第二步。

1
void get(int n) {
2
  for (int i = 2; i <= n; i++) {
3
    if (!vis[i]) {
4
      prime[cnt++] = i;
5
    }
6
    for (int j = 2; i * j <= n; j ++) vis[i * j] = true;
7
  }
8
}

其中，prime数组存储质数，vis数组用于标记（即上文中“划去数字”），变量cnt则存储$[2,N]$中质数的个数。

复杂度：$\mathcal O(n\ln{n})$

适用范围：普及T2及以下

但是继续观察算法发现：我们其实无需将所有$i$的倍数删去，只需删去前一步得出的质数的所有倍数即可。 这与前文介绍的埃氏法核心相符。因此将$j$循环迁移至条件判断中即可：

1
void get(int n) {
2
  for (int i = 2; i <= n; i++) {
3
    if (!vis[i]) {
4
      prime[cnt++] = i;
5
      for (int j = i + i; j <= n; j += i) vis[j] = true;
6
    }
7
  }
8
}

优化复杂度：$\mathcal O(n\log{\log n})$

适用范围：普及T3及以下

线性筛/欧拉筛：实质是埃氏筛的线性优化。因为在埃氏筛中，有些数字被重复筛了多次（例如30会被2、3、5筛到）。本着线性优化的原则，我们需要找到一个方法，使得每个合数仅被筛选一次。主要思想如下：

我们发现，线性筛和埃氏筛均使用了质数的$n$倍为合数的结论。我们只需要保证每一个数仅被它自身的最小质因数筛出即可。即对于数字$m$，$m\cdot p_i$是一个合数，且$m\cdot p_i$只会被$p_i$筛出。

1
void get(int n) {
2
  for (int i = 2; i <= n; i++) {
3
    if (!vis[i]) prime[cnt++] = j;
4
    for (int j = 1; prime[j] <= n / i; j++) {
5
      vis[prime[j] * i] = true;
6
      if (i % prime[j] == 0) break;
7
    }
8
  }
9
}

复杂度：$\mathcal O(n)$

适用范围：普及、提高

例题：

1. P5736 【深基7.例2】质数筛
2. P5723 【深基4.例13】质数口袋

Div1.  因数分解法#

试除法：万能暴力解法。即遍历$[2,\sqrt n]$间的所有数$m$，若可以整除$n$，则$m$和$\frac{n}{m}$均为$n$的因数。特殊情况：$\sqrt n$为整数时，因数仅有$\sqrt n$本身，因此需特判。

1
vector<int> get(int n) {
2
  vector<int> ret;
3
  for (int i = 2; i * i <= n; i++) {
4
    if (n % i == 0) {
5
      ret.push_back(i);
6
      ret.push_back(n / i);
7
    }
8
    if (n % (i * i) == 0) ret.pop_back();
9
  }
10
  sort(ret.begin(), ret.end());
11
  return ret;
12
}

复杂度：$\mathcal O(\sqrt n)$

适用范围：普及T1

Div2.最大公约数#

辗转相除法： 又是我们大名鼎鼎的欧几里得老先生提出的一套公约数算法，整个算极其简洁：核心只有一行，即：

两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

可以写出：

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

但是为什么$gcd(a,b)=gcd(a,a\bmod b)$呢？我们可以通过以下方法证明：

假设如下关系：$A=B\cdot C + D$。其中被除数$A$，除数$B$，商$C$，余数$D$。则$A\bmod B=A\bmod C=D$。

首先证明充分性：令$A=a\cdot k$、$B=b\cdot k$，即二者有相同因子$k$。

代入初始除法算式得：$D=A-B\cdot C\rightarrow a\cdot k-b\cdot k\cdot C\rightarrow k(a-b\cdot C)$

接着由于加减乘法的封闭性，即一个整数进行加减乘运算得到的结果同样是一个整数。可以得出：$D=k\cdot N\mid N\in \mathbb{N_+}$。即$D$（$A\bmod B$）与$A$有共同因子。

接下来证必要性。令$B=b\cdot q$、$D=d\cdot q$

Stein算法： 上一个方法的明显缺点在于，它处理大质数的效率并不好（但总体来说是很好的），因为它使用了取余运算，这会减慢一些速度。可以理解，生在2000多年前——一个没有电脑和OI的古希腊社会，这个算法已经足够兼顾常规效率和手推难度了。但是步入21世纪，加快的生活节奏毒瘤数据使得人们对更快算法的需求空前高涨。Stein算法便应运而生。

算法流程如下：

1. 任意给定两个正整数，先判断它们是否都是偶数，若是，则用2约简，若不是，则执行第二步。
2. 若两数是一奇一偶，则偶数除以2，直至两数都成为奇数。再以较大的数减较小的数，接着取所得的差与较小的数，若两数一奇一偶，仍然偶数除以2，直至两数都成为奇数。再次以大数减小数。不断重复这个操作，直到所得的减数和差相等为止。
3. 两数相等时，第一步中约掉的若干个2与第二步中最终的等数的乘积就是所求的最大公约数。

1
int gcd(int a, int b) {
2
  int p = 0, t;
3
  if (!(1 & a) && !(1 & b)) {
4
    a >>= 1;
5
    b >>= 1;
6
    p++;
7
  }
8
  while (!(1 & a)) a >>= 1;
9
  while (!(1 & b)) b >>= 1;
10
  if (a < b) {
11
    t = a;
12
    a = b;
13
    b = t;
14
  }
15
  while (a = ((a - b) >> 1)) {
16
    while (!(1 & a)) a >>= 1;
17
    if (a < b) {
18
      t = a;
19
      a = b;
20
      b = t;
21
    }
22
  }
23
  return b << p;
24
}

这个算法的优点在于：它大大优化了大质数的运算。但可惜的是，它的代码量膨胀了8倍，因此不太建议赛时使用。毕竟C++都给你内置了__gcd()函数嘛，干嘛不偷个懒？

Div3. 最小公倍数#

我们可以简单概括成一句话：

两个数的最小公倍数等于这两个数的乘积与这两个数最大公约数的商

即：$lca(a,b)=\frac{a\cdot b}{gcd(a,b)}$

凭啥呀？

我们假设两个数$A$和$B$有最大公约数$x$，则$A=a\cdot x$，且$B=b\cdot x$。并且$a$和$b$一定互质（若不互质，$A$和$B$的最大公约数就不会是$x$，而是一个比$x$大的值）。

由乘法交换律，可知：$A\cdot B = B\cdot A\rightarrow A\cdot b \cdot x=B\cdot a\cdot x$

消去$x$得：$A\cdot b=B\cdot a$。因为$a$、$b$互质，所以$A\cdot b$或者$B\cdot a$即为两个数的最小公倍数。得证。

例题：

1. P1075 [NOIP2012 普及组] 质因数分解
2. P2424 约数和 （需要逆向思维）

Div1. 欧拉函数推导#

问：论牧师欧拉有多么的高产

答：平均每年800页数学论文你说高不高产嘛

欧拉函数，记作$\varphi(n)$。表示$[1,n)$中与$n$互质的数的个数，即$\forall m\in [1,n)$，满足$gcd(n,m)=1$的$m$的总个数即为$\varphi(n)$的值。举个例子，$\varphi(3)=2$，因为在$[1,3)$中，$1$和$2$均与$3$互质。特殊地，$\varphi(1)=1$。

欧拉函数有如下计算公式：若$n$可被表示为$n=\prod\limits_{i=1}^{k}p_i^{\alpha_i}$（算术基本定理分解式）的形式，则$\varphi(n)=n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})=n*\prod\limits_{i=1}^{k}(1-\frac{1}{p_i})$。

推导思想即为用$n$减去所有$[1,n)$中所有与$n$不互质的数。在计算机上实现，首先需要分解质因数。思路如下：首先抛出第一个质因数$p_1$，那么将$[1,n]$中所有的$p_1$的倍数删去，因而可以保证筛出的数一定是$n$的质因子，否则他们将存在最大公约数$p_1$。那么能被$p_1$整除的数的个数（也就是$n$以内$p_1$的倍数个数）为$[\frac{n}{p_1}]$——其中的中括号代表整除。

因此我们离解出欧拉函数就进了一步了，我们的过渡式子就是$TS_1(n)=n-[\frac{n}{p_1}]-[\frac{n}{p_2}]-\dots-[\frac{n}{p_{k-1}}]-[\frac{n}{p_k}]$。

好耶

别急着好耶，我们可以发现一个小小的推导谬误（可能并不是很容易发现）。当我们用$p_2$去筛数时，使用的算式仍然是$[\frac{n}{p_2}]$。对于形如$p_1^np_2^m$的数，会被重复筛去多次，导致多减，最终结果会小于$\varphi(n)$。有些抽象，我们来看这张图：

易知$[1,30]$中可被$2$整除的数字共有$30\div 2=15$个，能被$5$整除的数字共有$30\div 5=6$个。但是如果说能被$2$和$5$整除的数字共有$15+6=21$个，显然不合常理，因为$10$、$20$、$30$都既能被$2$整除，也能被$5$整除，如果不加排除，他们将会被减去2次。因此需要补偿损失，正确的计算方法是（仅计算能被$2$和$5$整除的数的总个数）：

• 能被$2$整除的：$30\div 2=15$个
• 能被$5$整除的：$30\div 5=6$个
• 同时被$2$和$5$整除的：$30\div lca(2,5)=30 \div 10=3$个
• 总个数：$15+6-(2-1)\times 3=18$个（就是被绿圈和橙圈捆住的的数的个数）

那么对于$2$、$3$、$5$整除问题，中间的$30$被重复加了3次，需减去两次平衡收支。此即容斥原理的简单思想表示。

回到欧拉函数推导上来：过渡公式$TS_1$中的容斥问题可以解决一部分了。对于可同时被两个不同质数整除的数（例如$6=2\times3$、$15=3\times5$），我们加上它的总个数。 得到$TS_2=TS_1+[\frac{n}{p_1p_2}]+[\frac{n}{p_1p_3}]+\dots+[\frac{n}{p_1p_k}]+[\frac{n}{p_2p_3}]+[\frac{n}{p_2p_4}]+\dots+[\frac{n}{p_{k-1}p_k}]$。

当然这又有一个小问题没完没了了是不是？：对于$p_1\;p_2\;p_3$的公倍数，会被先减去3次，然后被上一步的操作加上3次，总体不加不减。还是回到上图：中间的$30$会被每个颜色的圈先减去一次、共3次，上一步的补偿操作，可以看作又被橙绿圈（橙圈和绿圈的交集）、蓝绿圈、蓝橙圈一共加上了3次。减3次加3次相当于没动，为了让它被算上，我们需要加上它，对于$\varphi(n)$则是全部减去（因为括号外有减号需要变号，不要忘记$\varphi(n)$是由一系列不合规的数字个数相减得来的）。得到我们的过渡态3：$TS_3=TS_2-[\frac{n}{p_1p_2p_3}]-[\frac{n}{p_1p_2p_4}]-[\frac{n}{p_1p_2p_5}]-\dots-[\frac{n}{p_{k-2}p_{k-1}p_{k}}]$

又是如上的容斥判断，这里我们省去讨论。将最终的产物合并得到：$\varphi(n)=n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_{k-1}})(1-\frac{1}{p_k})$！（我不会合并，但是你可以把$\varphi(n)$括号拆开看看是不是上述形式。总之，欧拉牛逼！）

$QED$，好耶！终于可以好耶了……

Div2. 欧拉函数代码实现#

主要是如果压成一个Div会非常的长，因此这里新开一个Div2

我们明确了欧拉函数的推导，接下来就是整理思路写代码的时间了！我们也只需跟着原始思路走就可以了。再次回忆一下：首先我们需要筛出质因数，除去它的所有倍数，再用公式$\varphi(n)=n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_{k-1}})(1-\frac{1}{p_k})$代入$p_i$就可以了。

1
long long eular(int n) {
2
  long long res = n;
3
  for (int i = 2; i * i <= n; i++) {
4
    if (n % i == 0) {
5
      res = res * (i - 1) / i;
6
      while (n % i == 0) n /= i;
7
    }
8
  }
9
  if (n > 1) res = res * (n - 1) / n;
10
  return res;
11
}

时间复杂度：$\mathcal O(\sqrt n)$

适用范围：All Clear

Div3. 欧拉函数推论#

1. 若$p$为质数，则$\varphi(p)=p-1$

让我们回到欧拉函数的定义上去：$\varphi(i)$是$[1,i]$中与$i$互质的数的个数（特殊地，$\varphi(1)=1$）。那么对于$p$这个质数，有多少数与它互质呢？

很显然，答案是$p-1$个！因为$p$的质因子只有$p$本身，若不止$p$一个质因子，很显然它不是一个质数。因此$\varphi(p)=p(1-\frac{1}{p})=p-1$。

2. 假设$p_k$是一个质数，$p_k\mid i$（或$i\bmod p_k=0$），且$\varphi(i)$的值已知，那么$\varphi(p_k*i)=p_k\cdot\varphi(i)$

凭啥呀？

因为$p_k$已经是一个质数，换句话说：在这个条件下$p_k$是$p_k*i$的一个质因子。在计算$\varphi(i)$时，$p_k$就已经作为一个质因子以$(1-\frac{1}{p_k})$的形式乘进去了。此时$\varphi(i)$可以写作

$\varphi(i)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})\dots (1-\frac{1}{p_n})\dots \dots(1)$

那么函数值多乘了一个$p_k$

$\varphi(p_k*i)=p_k\cdot i(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})\dots (1-\frac{1}{p_n})\dots\dots(2)$

我们发现：(2)式中包含了(1)式，只是头上乘以了$p_k$。因而得到$\varphi(p_k*i)=\varphi(i)\cdot p_k$

3. 假设$p_k$是一个质数，$p_k\nmid i$（或$i\bmod p_k\neq0$），且$\varphi(i)$的值已知，那么$\varphi(p_k*i)=p_k\cdot\varphi(i)\cdot(1-\frac{1}{p_k})= \varphi(i)\cdot(p_k-1)$

这东西长得和性质2很相似，唯一不同的是$p_k$不再是$i$的一个质因子了。但是$p_k$变成了$p_k*i$的质因子。因此我们计算$\varphi(p_k*i)$的值时，不仅需要在头部乘上$p_k$，而且还需要将$(1-\frac{1}{p_k})$乘进去：

$\varphi(p_k*i)=p_k\cdot i\cdot (1-\frac{1}{p_1})\dots(1-\frac{1}{p_n})(1-\frac{1}{p_k})$

因为$p_k\cdot (1-\frac{1}{p_k})=p_k-1$，所以得到性质3，即$\varphi(p_k*i)=p_k\cdot\varphi(i)\cdot(1-\frac{1}{p_k})= \varphi(i)\cdot(p_k-1)$。

这三个性质将作为重点性质出现在欧拉函数筛法中。

Div4. 欧拉函数线性筛#

我们已经接触了简单的欧拉函数计算方法，那么又该如何解决形如：“给定一个正整数$i\in [x,y]$，求$\sum\limits_{i=x}^{y}\varphi(i)$的值”的问题呢？

考虑继续使用上面的朴素算法，时间复杂度将会是$n\sqrt n$。明显无法满足需求，更何况，每个数与每个数之间的$\varphi$值之间有一种推导关系，使得我们无需每次重新计算$\varphi$值，而是用已经求出的$\varphi(n)$来线性推出$\varphi(i)$的值。

欧拉函数涉及到质因子的拆分，我们又需要在线性时间内求各种质数。自然而然想到了先前所学的线性筛：

1
int primes[N];
2
bool st[N];
3
int cnt = 0;
4

5
void sieve(int n) {
6
  for (int i = 2; i <= n; i++) {
7
    if (!st[i]) primes[++cnt] = i;
8
    for (int j = 1; primes[j] * i <= n; j++) {
9
      st[primes[j] * i] = true;
10
      if (i % primes[j] == 0) break;
11
    }
12
  }
13
}

我们运用这段代码可以得出$[1,n]$范围内所有的质数，用st[N]数组可以筛出所有的合数。也就是说对于筛出的合数，我们能够得知组成它的质因子是什么，比如st[primes[j]*i]=true;这一行代码。接着套用上述三种性质，我们可以得出$\varphi$值。

此时我们就需要新建一个phi[N]数组来存储每个数的$\varphi$值，并且在代码中三个地方加入对于三种性质的公式：

1
typedef long long ll;
2

3
ll primes[N];
4
bool st[N];
5
int cnt = 0;
6
ll phi[N];
7

8
void phi_sieve(int n) {
9
  for (int i = 2; i <= n; i++) {
10
    if (!st[i]) {
11
      primes[++cnt] = i;
12
      phi[i] = i - 1;
13
    }
14
    for (int j = 1; primes[j] * i <= n; j++) {
15
      st[primes[j] * i] = true;
16
      if (i % primes[j] == 0) {
17
        phi[primes[j] * i] = phi[i] * primes[j];
18
        break;
19
      }
20
      phi[primes[j] * i] = phi[i] * (primes[j] - 1);
21
    }
22
  }
23
}

没错我开了long long防止爆int

时间复杂度：$\mathcal O(n)$

适用范围：普及&提高

对于开头提出的求和问题，遍历phi[1]到phi[n]的所有值求和即可。

Div5. 欧拉定理#

若正整数$a$与$n$互质，则有$a^{\varphi(n)}\equiv1\pmod n$

对于它的证明，百度百科中如此写到：

取$m$的缩系$a_1,a_2,\dots,a_{\varphi(m)}$，故$aa_1,aa_2,\dots,aa_{\varphi(m)}$也为$m$的缩系。有$\prod\limits_{i=1}^{\varphi(m)}a_i\equiv\prod\limits_{i=1}^{\varphi(m)}aa_i\equiv a_{\varphi(m)}\prod\limits_{i=1}^{\varphi(m)}a_i\pmod m$

通俗来讲就是这样：

1. 在$[1,n]$中取所有与$n$互质的数$a_1,a_2\dots,a_{\varphi(n)}$，很容易知道这样的$a$共有$\varphi(n)$个（根据欧拉函数定义得来）。它们都与$n$互质。
2. 给这列数同时乘上$a$，得到$aa_1,aa_2,\dots,aa_{\varphi(n)}$。它们也都和$n$互质，并且各不相同。
3. 提出括号里乘了$\varphi(n)$次的$a$，得到以下关系式：$a^{\varphi(n)}[a_1a_2\dots a_{\varphi(n)}]\equiv a_1a_2\dots a_{\varphi(n)}\pmod n$
4. 那么根据同余号两端的消去原则（左右两端两个项相同且与模$n$互质），可以消去$a_1a_2\dots a_{\varphi(n)}$。得到$a^{\varphi(n)}\equiv1\pmod n$，欧拉定理得证。
5. 特殊地，如果$p$是一个质数，有$a^{\varphi(p)}\equiv1\pmod p\Rightarrow a^{p-1}\equiv1\pmod p$。这被称作费马小定理（先前的费马素性检验就是基于这个原理编写的）。

真不知道明明可以写得通俗点为什么非得省那点空间写看起来那么高深莫测的专业术语，真的是只写给自己看的。

Div6. 降幂算法#

尤其对于绿题以上的题目，题面中可能出现“答案可能很大，请对大质数$p$取余”的字样。这意味着题目可能涉及到大规模的幂运算，需要我们用简便的方法计算幂。对于一般的题目，我们使用快速幂。

快速幂：快速幂思想如下：

$a^b= \begin{cases}a^{ \frac{b}{2}}\times a^{ \frac{b}{2}},& b\bmod 2=0\\a\times a^{ \frac{b-1}{2}}\times a^{ \frac{b-1}{2}},&b\bmod2=1 \end{cases}$

我们将指数$b$分解为若干$2^n$的和（二进制表示），例如：$a^{11}=a^{2^0}\cdot a^{2^1}\cdot a^{2^3}$，因为$(11)_{10}=(1011)_2$。因而不必将$a$连续乘11次，效率大幅提升。

1
typedef long long ll;
2

3
int qpow(int a, int k, int p) {
4
  int res = 1;
5
  while (k) {
6
    if (k & 1) res = (ll) res * a % p;
7
    a = a * a % p;
8
    k >>= 1;
9
  }
10
  return res;
11
}

时间复杂度：$\mathcal O(\log n)$

适用范围：基本All Clear

欧拉降幂：上面方法一个缺点在于无法处理过大的指数，在处理类似于$a^{2^n}$的计算时将会疯狂掉san。接下来介绍一种使用上面讲到的欧拉定理来解决大指数幂运算的方法。

欧拉降幂核心公式：$a^k\bmod p=a^{k\bmod\varphi(p)+\varphi(p)}\bmod p$（又称 扩展欧拉定理 ）

也就是说：我们只需要算出$q=k\bmod\varphi(p)+\varphi(p)$的值，再用快速幂算法，将$q$作为新指数带入计算即可。当然，这里的$k$可能会爆long long，因此可以选择使用字符串进行高精度计算。

1
typedef long long ll;
2

3
ll primes[N];
4
bool st[N];
5
int cnt = 0;
6

7
int qpow(int a, int k, int p) {
8
  int res = 1;
9
  while (k) {
10
    if (k & 1) res = (ll) res * a % p;
11
    a = a * a % p;
12
    k >>= 1;
13
  }
14
  return res;
15
}
16

17
ll eular(int n) {
18
  ll res = 0;
19
  for (int i = 2; i <= n; i++) {
20
    if (!st[i]) {
21
      primes[++cnt] = i;
22
      res = res * (i - 1) / i;
23
      while (n % i == 0) n /= i;
24
    }
25
    for (int j = 1; i * primes[j] <= n; j++) {
26
      st[i * primes[j]] = true;
27
      if (i % primes[j] == 0) break;
28
    }
29
  }
30
  if (n > 1) res = res * (n - 1) / n;
31
  return res;
32
}
33

34
int edp(int a, string k, int p) {
35
  ll phi = eular(p);
36
  int drop = 0;
37
  for (int i = 0; i < k.length(); i++) {
38
    drop *= 10;
39
    drop += k[i] % phi;
40
  }
41
  drop += phi;
42
  return qpow(a, drop, p);
43
}

其中eular(int n)函数用于计算欧拉函数的值、edp(int a, string k, int p)用于计算降幂后的指数、qpow(int a, int k, int p)是快速幂算法。

时间复杂度：$\mathcal O(\log n)$

适用范围：所有

扩展欧拉定理可谓是欧拉定理的一般形式，它的定义如下：对于任意正整数$a$、$k$、$p$，满足：

$a^k\equiv\begin{cases}a^k&(\bmod\;p ),gcd(a,p)\neq1,k<\varphi(p)\\a^{k\bmod\varphi(p)+\varphi(p)}&(\bmod\;p),gcd(a,p)\neq1,k\geq\varphi(p)\\a^{k\bmod\varphi(p)}&(\bmod\;p),gcd(a,p)=1\end{cases}$

其中第二个式子就是欧拉降幂的核心公式。

扩展欧拉定理的证明见这里。因为太复杂了我不会证

例题：

1. P2158 [SDOI2008] 仪仗队 （欧拉函数板子）
2. P1447 [NOI2010] 能量采集（上一个问题的变式）
3. P1226 [模板] 快速幂
4. P5091 [模板] 扩展欧拉定理 （欧拉降幂）
5. P4139 上帝与集合的正确用法 （欧拉降幂+递归）

Div.1 裴蜀定理#

很多人会把他读成裴除（chú）（比如我的某位好友），这个名词正确的读法是裴蜀（shǔ）。或者可以直接改称作“贝祖定理”，它的提出者艾蒂安·裴蜀估计怎么也没想到后人居然连他的名字都读不对（想想如果这种事情发生到你身上会怎么样）。你也可以读他名字的法语发音$B\acute ezout$（显得你很优雅且有文化）。

切入正题，裴蜀定理表述为：对于任意正整数$a$，$b$，总有整数$x$、$y$，使得$ax+by=(a,b)$，其中$(a,b)$等价于$gcd(a,b)$，是数论中最大公约数的表述方式。

首先可以知道$at+bn=d\;\;\;(n,t\in\mathbb Z\;\;\;n,t\neq0)$且$(a,b)\mid d$，因为$a$和$b$都具有约数$(a,b)$，让他们分别乘上另两个数$t$和$n$并不会改变$(a,b)$这一约数。所以假设$d=k\cdot(a,b),k\in\mathbb Z$，有$a\frac{t}{k}+b\frac{n}{k}=(a,b)$。在这里，$x=\frac{t}{k}\;\;y=\frac{n}{k}$。

Div2. 扩展欧几里得（EXGCD）#

加了“扩展”二字是不是感觉逼格上来了？

扩展欧几里得算法用于求出线性同余方程的解。线性同余方程，即形如$ax\equiv b\pmod p$的方程，我们需要求出$x$的值。

回忆一下欧几里得算法的核心思路：$(a,b)=\begin{cases}(a,a\bmod b)&a\bmod b\neq0\\a&a\bmod b=0\end{cases}$。

再看看刚刚讲到的裴蜀定理，发现$(a\bmod b)x+by=k\cdot(a,a\bmod b)=k\cdot(a,b)=d$。根据余数的定义，有：$(a-\lfloor\frac{a}{b}\rfloor\cdot b)x+by=d$。

那么我们的任务就是求出这里的$x$和$y$值，因此拆开括号，整理出$a$和$b$的系数：$ax+b(y-\lfloor\frac{a}{b}\rfloor x)=d$。观察裴蜀定理的形式：$ax+by=(a,b)$，我们得出的式子中，$y$变成了$y-\lfloor\frac{a}{b}\rfloor x$。因此每次递归时需要将$y$的值减去$\lfloor\frac{a}{b}\rfloor x$。