数论 $1$

$1.$ 质数

~~定义就不说了吧。~~

性质 $\&$ 定理

质数 $p$ 有且仅有两个质因子 $1$ 和 $p$ 。
质数有无穷个。
$[1,\, n]$ 中的质数个数约为 $\dfrac{n}{\ln n}$ (此结论可用来大致估算某些数论题的数据范围)。
任何一个大于 $1$ 的整数 $N$ 都可以分解成 $N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})$ 的形式，如果不计各个质因数的顺序，那么这种分解是惟一的。

筛质数——线性筛法

线性筛法，顾名思义，可以筛出 $[1,\, n]$ 内的所有质数，时间复杂度为 $\mathcal O (n)$ 。

int primes[N], cnt;
// primes存放所有的质数，cnt是质数的数量
// 这里的primes数组可以根据N的范围，结合质数定理，适当开小一点，这里就不管了
int st[N];
// st[i]记录每个数是否是质数

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

$2.$ 约数

~~定义还是就不说了吧。~~

性质 $\&$ 定理

对于任何一个大于 $1$ 的整数 $N$，如果将其分解质因数为 $N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})$ 的形式，那么 $N$ 的正约数个数为 ${\large \prod}\limits_{i = 1}^k \, (\alpha_i + 1)$ ， $N$ 的所有正约数的和为 ${\large \prod}\limits_{i = 1}^k \left({\large \sum}\limits_{j = 0}^{\alpha_i} \, p_i^j\right)$ 。
$2^{31}$ 内约数个数最多的数有 $1600$ 个约数；$2^{63}$ 内约数个数最多的数有 $138240$ 个约数。

求约数个数

对于要重复计算多次的，先筛出质数，代码效率会有所提高。

int get_divisors(int x){
	int res = 1, s;
	for(int i = 0; primes[i] < x / primes[i]; ++i){
		int p = primes[i];
		s = 0;
		while(x % p == 0){
			++s;
			x /= p;
		}
		res *= s + 1;
	}
	if(x > 1) res *= 2;
    // 这里一定记得判断是否有还没除尽的质因子
	
	return res;
}

$3.$ 欧拉函数 $\varphi$

定义

$\varphi(n)$ 表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。

计算方法

对于任何一个大于 $1$ 的整数 $N$，如果将其分解质因数为 $N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})$ 的形式，那么：

\[\varphi(N) = N \prod\limits_{i = 1}^k \left( 1 - \cfrac 1{p_i} \right) \]

特别地，$\varphi(1) = 1$ 。

性质 $\&$ 定理

有一堆，慢慢看吧，理性了解，证明的话有兴趣可以自己去搜索。

对于质数 $p$，$\varphi(p) = p - 1$ 。
若 $p$ 为质数，$n = p^k \ (k \in \mathbb{N^*})$ ，那么 $\varphi(n) = p^k - p^{k - 1}$ 。
若 $a \mid n$，那么 $\varphi(an) = a \varphi(n)$ 。
若 $(n, m) = 1$ ，那么 $\varphi(n) \varphi(m) = \varphi(nm)$ 。
当 $n > 2$ 时，$\varphi(n)$ 为偶数。
若 $n$ 为大于 $1$ 的正整数，那么在小于等于 $n$ 的正整数中，与 $n$ 互质的数之和为 $\dfrac{n \varphi(n)}{2}$ 。
$ n = {\large \sum}\limits_{d \mid n} \varphi(d)$ 。

$4.$ 线性筛法求欧拉函数 $\varphi$

利用线性筛法以及欧拉函数的性质，可以筛出 $[1,\, n]$ 内的所有质数，顺便求出 $[1,\, n]$ 内的所有整数的欧拉函数，时间复杂度为 $\mathcal O (n)$ 。

int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!st[i]){
            primes[cnt++] = i;
            phi[i] = i - 1;
            // 前面的性质1
        }
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0){
                phi[i * primes[j]] = phi[i] * primes[j];
                // 性质3
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            // 这个可以直接由计算方法推出来
        }
    }
}

$5.$ 欧拉定理

$\text{Content}$

若 $a, n \in \mathbb{N^*}$ ，且 $(a, n) = 1$ ，则有：

\[\large a^{\varphi(n)} \equiv 1 \pmod n \]

特别地，当 $n \in \mathbb P$ 时，这就成了费马小定理

若 $p \in \mathbb P$ ，且 $p \nmid a$ 则有：

\[\large a^{p - 1} \equiv 1 \pmod p \]

$6.$ 综合应用

$\texttt{E}\color{red}{\texttt{g} 1}$ AcWing 197. 阶乘分解

给定整数 $N$，将 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 。

按照 $p_i$ 由小到大的顺序输出。

$3 \le N \le 10^6$

首先 $N \le 10^6$ ，所以 $N!$ 会很大，直接分解肯定不行，考虑从 $N!$ 的特殊性质入手。

$N! = 1 \times 2 \times \cdots \times N$

那么对于一个质数 $p$ ，$1 \sim N$ 中的 $p,2p,\dots,kp$ （ $p$ 的倍数）肯定含有质因子 $p$ ，可以很容易得出个数为 $\left\lfloor \dfrac Np \right\rfloor$ 。

但这还会漏掉一些，如果一个数中含有 $2$ 个因子 $p$ ，会被漏算一次，因此还需要加上 $1 \sim N$ 中的 $p^2,2p^2,\dots,kp^2$ ，有 $\left\lfloor \dfrac N{p^2} \right\rfloor$ 个。

以此类推，$N!$ 中某个质因子 $p$ 的次数为

\[\sum\limits_{k = 1}^{\left\lfloor \log_p n \right\rfloor} \left\lfloor \dfrac N{p^k} \right\rfloor \]

那么接下来枚举所有小于等于 $N$ 的质数，再分别求和就好了，时间复杂度 $\mathcal O(N)$ 左右吧~~（有点不好分析，反正过肯定是没问题的）~~。

$\mathcal{Code}$

#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;

int n;
int primes[N], cnt;
bool st[N];

void init(int n){
	for(int i = 2; i <= n; ++i){
		if(!st[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0) break;
		}
	}
}

int main(){
	scanf("%d", &n);
	init(n);
	
	for(int i = 0; i < cnt; ++i){
		int p = primes[i], s = 0;
		int k = n;
		while(k){
			s += k / p;
			k /= p;
		}
		printf("%d %d\n", p, s);
	}
	
	return 0;
}

$\texttt{E}\color{red}{\texttt{g} 2}$ 洛谷P2158 [SDOI2008] 仪仗队

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 $n \times n$ 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

对于 $100 \%$ 的数据，$1 \le n \le 40000$。

首先进行分析，将仪仗队放在一个平面直角坐标系中，无法看到的学生是因为被在同一条从原点出发的直线上的前面的学生挡住了。

那么可以得到学生能被看到的条件是横纵坐标互质。

答案就是：

\[\sum_{i = 1}^{n - 1} \sum_{j = 1}^{n - 1} [\gcd(i,j) = 1] + 2 \]

最后加上的两个是 $(0,1)$ 和 $(1,0)$ 。

上式变一下（配合着图可能更好理解一些）：

\[2 \sum_{i = 1}^{n - 1} \sum_{j = 1}^{i} [\gcd(i, j) = 1] + 1 \]

这里我们惊喜的发现，可以用 $\varphi(i)$ 来表示 ${\Large \sum}\limits_{j = 1}^{i} \, [\gcd(i, j) = 1]$

于是，最后的柿子就出来咯：

\[{\rm Ans} = 2 \sum_{i = 1}^{n - 1} \varphi(i) + 1 \]

当然，当 $n = 1$ 时，是没有学生的，也不满足上面的结论，需要特判一下。

代码就很好实现啦，用线性筛求个欧拉函数就可以 $\color{#52C41A}{\text{AC}}$ 此题，$\mathcal O(n)$ 根本不虚。

$\mathcal{Code}$

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 40010;

int T, n, res = 1;	// +1跑到这里来了哦
int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; ++i){
		if(!st[i]){
			primes[cnt++] = i;
			phi[i] = i - 1;
		}
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0){
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}                          
	}
}

int main(){
	scanf("%d", &n);
	if(n == 1){
		puts("0");
		return 0;
	}
	init(n);
	
	for(int i = 1; i < n; ++i) res += 2 * phi[i];
	
	printf("%d\n", res);
	return 0;
}

$\texttt{E}\color{red}{\texttt{g} 3}$ AcWing 202. 最幸运的数字

题目描述

$8$ 是中国的幸运数字，如果一个数字的每一位都由 $8$ 构成则该数字被称作是幸运数字。

现在给定一个正整数 $L$，请问至少多少个 $8$ 连在一起组成的正整数（即最小幸运数字）是 $L$ 的倍数。

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含一个整数 $L$。

当输入用例 $L = 0$ 时，表示输入终止，该用例无需处理。

输出格式

每组测试用例输出结果占一行。

结果为 Case i: + 一个整数 $N$ ，$N$ 代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在，则 $N = 0$。

数据范围

$1 \le L \le 2 \times 10^9$

先简化一下题意：

求最小的 $n$ ，使得 $L \mid \underbrace{ 88\dots8}_{n个8}$ 。

再变一下

\[L \, \left| \, \underbrace{88\dots8}_{n个8} \right. \quad \Longrightarrow \quad L \, \left| \, \cfrac 89 \times \underbrace{99\dots9}_{n个9} \right. \quad \Longrightarrow \quad L \, \left| \, \cfrac 89 (10^n - 1) \right. \quad \Longrightarrow \quad 9L \mid 8(10^n - 1) \]

\[\Longrightarrow \quad \cfrac{9L}{\gcd(L, 8)} \, \left| \, \cfrac 8{\gcd(L, 8)} (10^n - 1) \right. \]

易得 $\cfrac{9L}{\gcd(L, 8)}$ 与 $\cfrac 8{\gcd(L, 8)}$ 互质。

那么，设 $d = \gcd(L, 8)$

\[\left. \cfrac{9L}d \, \right| \, (10^n - 1) \]

再设 $C = \dfrac{9L}d$ ，则 $C \mid (10^n - 1)$ ，这里可以进一步转化成同余方程 $10^n \equiv 1 \pmod C$ 。

那之后又怎么办呢？

这时候，之前的 欧拉定理 就派上用场了，现在就差一个条件 $\gcd(10, C) = 1$。

可以发现，若 $\gcd(10, C) \ne 1$ ，那么 $10^n \bmod C$ 肯定不可能是 $1$，也就肯定不满足同余方程。

于是，我们可以判断 $10$ 和 $C$ 是否互质，如果不互质，则无解。

如果互质，那么 $n = \varphi(C)$ 就是一个特解，但还有一个问题，这并不能保证 $n$ 是同余方程最小的正整数解。

这里其实还有一个推论，设 $x$ 为满足要求的最小正整数解，那么一定有 $x \mid \varphi(C)$ 。

证明

假设 $x$ 为满足要求的最小正整数解，且 $x \nmid \varphi(C)$ 。

不妨设 $\varphi(C) = px + q \ (p,q \in \mathbb{N^*} , \, 1 \le q < x)$

于是 $10^x \equiv 1 \pmod C$

两边同时 $p$ 次方，得 $10^{px} \equiv 1 \pmod C$ 。

又因为 $10^{px + q} \equiv 1 \pmod C$ 。

得到 $10^q \equiv 1 \pmod C$ ，这就找到了一个比 $x$ 更小的正整数解 $q$ ，与假设矛盾，故假设不成立。

于是命题 “设 $x$ 为满足要求的最小正整数解，那么一定有 $x \mid \varphi(C)$ ” 成立。

$\mathcal{Q.E.D.}$

上面说了一大堆，接下来的代码就可以写出来了。

还有本题的一个坑点，数据太毒，在快速幂的模数很大的情况下，会爆 $\tt{long \ long}$ ，我懒得写光速乘，就直接用 $\tt{\_\_int128}$ 了。

#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 1.4e5;
const ll INF = 1.01e18;

inline ll Min(ll a, ll b){return a < b ? a : b;}

int T = 1;
int primes[N / 10], cnt;
bool st[N];
ll L;

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

inline ll qpow(ll a, ll k, ll mod){
	ll res = 1;
	while(k){
		if(k & 1) res = (__int128)res * a % mod;
		a = (__int128)a * a % mod;
		k >>= 1;
	}
	
	return res;
}

inline ll get_phi(ll x){
	ll res = x;
	for(int i = 0; primes[i] <= x / primes[i]; ++i){
	    int p = primes[i];
		if(x % p == 0){
			while(x % p == 0) x /= p;
			res = res / p * (p - 1);
		}
	}
	if(x > 1) res = res / x * (x - 1);
	return res;
}

int main(){
	init(N - 1);
	while(scanf("%lld", &L), L){
		int d = 1;
		while(L % (d * 2) == 0 && d * 2 <= 8) d *= 2;
		// 求d（即gcd(L, 8)）
		ll c = 9 * L / d;
		// 求C
		
		ll phi = get_phi(c), ans = INF;
		// 这里其实每次单独求欧拉函数会更快，提前筛好质数会更快一些。
		
		if(c % 2 == 0 || c % 5 == 0) ans = 0;
		// 判断10和C是否互质
		
		for(ll i = 1; i <= phi / i; ++i)
			if(phi % i == 0){
				// 枚举phi(C)的所有约数，并判断是否满足同余方程
				if(qpow(10, i, c) == 1) ans = Min(ans, i);
				else if(qpow(10, phi / i, c) == 1) ans = Min(ans, phi / i);
			}
		
		printf("Case %d: %lld\n", T++, ans);
	}
	
	return 0;
}

时间复杂度分析：

设数据组数为 $T$

每次求 $\varphi(C)$ 加上提前筛质数是 $\mathcal O\left(\dfrac{\sqrt{L} }{\log \sqrt{L}} \right)$ 的。

每次枚举 $\varphi(C)$ 的所有约数并判断是否满足同余方程是 $\mathcal O \left(\sqrt L \log\sqrt L \right)$ 的。

那么总的复杂度就是 $\mathcal O \left(\sqrt L + T\sqrt L\left(\dfrac 1{\log\sqrt L} + \log\sqrt L \right) \right)$ ，本题的 $T$ 貌似很小，于是提前筛质数就只比不筛快了 $10\rm ms$ 左右。

那么忽略一下就是 $\mathcal O \left(T\sqrt L \log L \right)$ （$\log\sqrt L$ 和 $\log L$ 其实是同一数量级的，因为 $\log L = 2 \log\sqrt L$ ，这里为了简洁就直接忽略了常数）。