• 数论基础
  • 整除
  • 快速幂
  • gcd
    • 裴蜀定理
    • 应用
  • 扩展欧几里得算法
    • 算法描述
  • lcm
  • 同余
    • 性质
    • 应用
  • 逆元
  • 埃拉托色尼筛法
  • 杜教筛
  • Lagrange 插值
    • 孙子定理
    • 证明
    • 结论
    • 正文

数论基础

整除

对于两个整数 \(a\ ,\ b(a\neq 0)\) ，若 \(\exists k\in Z\) 使 \(ak=b\) 则称 \(a\) 整除 \(b\) ，记做 \(a|b\)

快速幂

P1226 【模板】快速幂||取余运算

快速幂用于快速计算 \(x^y\ \%\ mod\)

计算的思路是：将十进制的 \(y\) 看作二进制，再通过二进制下的一些运算统计答案

以下已默认为二进制下的情况

过程：

对于求 \(x^y\)，将 \(y\) 表示为二进制，如：\(105_{(10)} = 1101001_{(2)}\)

所以 \(x^y = x^{105} = x^{2^6+2^5+2^3+2^0}=x^{2^6}x^{2^5}x^{2^3}x^{2^0}\)

用变量 \(ans\) 统计答案

int ksm(int x, int y, int mod) {
	int ans = 1;
	for( ; y; y >>= 1, (x *= x) %= mod) if(y & 1) (ans *= x) %= mod;
	return ans;
}

注：\((a *= b) \%= mod\)的写法等价于 \(a = (a * b) \%mod\)

时间复杂度：\(O(log\ y)\)

gcd

两个数 \(a\) , \(b\) 的最大公约数

裴蜀定理

对于任意 \(x\ , \ y\) 都 \(\exists \ a,b\) 满足 \(ax+by=gcd(x,y)\)

应用

用来做题

可以用来证明奇奇怪怪的东西和推式子

信息上对于这东西常见的套路是枚举\(gcd\)

如：给你T组数据,求 \(\sum_{i=1}^n \sum_{j=1}^m gcd(i,j)\)

其中有一步是标准的枚举 \(gcd\)

\(\displaystyle \ \sum_{i=1}^n \sum_{j=1}^m gcd(i,j)\)

\(=\displaystyle \sum_{i=1}^n \sum_{j=1}^m \sum_{d|i,j}d[gcd(\frac id,\frac jd)==1]\)

\(\mathcal{Code}:\)

int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }

扩展欧几里得算法

P1082 [NOIP2012 提高组] 同余方程

算法描述

用于求解关于 \(x,y\) 的方程 \(ax+by = gcd(a, b)\) 的整数解

方程 \(ax + by = m\) 有解的必要条件是 \(m\ mod\ gcd(a, b) = 0\)

证明：

由已知条件易得： \(a\ mod\ gcd(a, b) = 0,b\ mod\ gcd(a, b) = 0\)

则有 \((ax + by)\ mod\ gcd(a, b) = 0\)

即为 \(m\ mod\ gcd(a, b) = 0\)

前置知识：欧几里得算法（辗转相除法）

欧几里得算法用于求解两个数的最大公因数

int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }

若我们已经知道以下的式子

则可以得出

则有

当 \(b = 0\) 时 \(ax = a\)

此时 \(y\) 最好取 \(0\)，因为在回溯时，\(y\) 的增长较快，容易数值越界

int Ex_gcd(int a, int b, int &x, int &y) {
	if(b == 0) return x = 1, y = 0, a;
	int ans = Ex_gcd(b, a % b, x, y);
	int tmp = x;
	x = y; y = tmp - a / b * y;
	return ans;
}

这样能够找到方程 \(ax+by=gcd(a, b)\) 的一组解

若要求解 \(x\) 为最小正整数的一组解，可由以下公式推导

则 \(x = (x \% b + b) \% b\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
int Ex_gcd(int a, int b, int &x, int &y) {
	if(b == 0) return x = 1, y = 0, a;
	int ans = Ex_gcd(b, a % b, x, y);
	int tmp = x;
	x = y; y = tmp - a / b * y;
	return ans;
}
int main() {
	int a = read(), b = read(), x, y;
	Ex_gcd(a, b, x, y);
	x = (x % b + b) % b;
	printf("%d\n", x);
	return 0;
}

例题：P1516 青蛙的约会

lcm

这个真没什么好说的

\(lcm\) 这东西在数论推柿子里因没有什么性质而遭到嫌弃

通常把 \(lcm\) 转化为 \(gcd\) 来做： \(lcm(i,j)=\frac {i*j}{gcd(i,j)}\)

注意，这一条性质只在两个数时才成立，其他情况不一定，比如

\(\frac {1*2*3*4*5}{gcd(1,2,3,4,5)} = 1*2*3*4*5 \neq lcm(1,2,3,4,5)\)

例题：P1891 疯狂LCM

同余

对于两整数 \(a\ ,\ b\) 若 \(\exists \ p \in prime\) 使 \(a\%p == b \% p\) 则称 \(a\) 与 \(b\) 在模 \(p\) 意义下同余

用符号表示则为 \(a \equiv b \ (mod \ p)\)

性质

对称性：$a \equiv b \ (mod \ p) \ \Rightarrow \ b \equiv a \ (mod \ p) $

可乘性：若 \(a \equiv b \ (mod \ p) \ , \ c \equiv d \ (mod \ p)\) ，则 \(ac \equiv bd \ (mod \ p)\)

应用

对于信息比较基本，没有什么应用，主要用在定理的证明和表达中

对于同余式 \(a \equiv b \ (mod \ p)\) ,可以转化为 \(a x+km=b\) 就可以应用 exgcd求了

特殊的，对于同余式 \(a \equiv 1 \ (mod \ p)\) 的一个解是 \(a\) 在模 \(p\) 意义下的逆元

逆元

对于整数\(a，p\)，\(\exists \ a^{-1}\) 满足 \(a*a^{-1} \ \equiv \ 1(mod \ p)\) 则称 \(a^{-1}\) 是 \(a\) 在模 \(p\) 意义下的逆元

主要用于除法取模问题

因为除法不对模运算封闭，所以逆元应运而生

求逆元主要用两种方法，一是费马小定理，二是 \(EX gcd\)，三是线性

只列出线性的代码

\(\mathcal{Code}:\)

inv[1] = 1;
for(int i = 2; i <= n; ++ i) inv[i] = ((p - p/i) * inv[p%i]) % p;

例题：P3811 乘法逆元，P5431 乘法逆元2

埃拉托色尼筛法

复杂度 $\Theta(n loglogn) $

所以建议用欧拉筛 \(\Theta(n)\)

在此讲一下原理

对于一个数 \(a\) , 则 \(k*a \ (k \in N^*)\) 一定不会在之后的循环中进入素数表，所以给他们打上标记

因为埃氏筛会对一些数重复筛，所以复杂度就不如欧拉筛优

\(\mathcal{Code}:\)

void calc(){
    for(int i = 2; i <= n; ++ i) {
        if(! vis[i]) prime[++ cnt] = i;
        for(int j = 1; j <= cnt; ++ j) {
            if(i * prime[j] <= n) vis[i * prime[j]] = 1;
        }
    } 
}

例题：P3383 线性筛素数

杜教筛

对于一个积性函数 \(f\)​，我们要求 \(\displaystyle \sum_{i=1}^nf(i)\)

\(\mathcal{Ans}\)：

令 \(S(n)=\displaystyle\sum_{i=1}^n f(i)\)，\(h=g*f\) (h，g为任意积性函数)

则 \(\displaystyle\sum\limits_{i=1}^{n}(f*g)(i)\)
\(\begin{aligned} &= \sum\limits_{i=1}^{n} \sum \limits _{d|i} g(d)f(\frac{i}{d}) \\ &= \sum \limits _{d=1}^{n} g(d)\sum\limits _{i=1}^{\lfloor \frac{n}{d}\rfloor } f(i) \\ &= \sum \limits _{d=1}^{n} g(d) S(\lfloor \frac{n}{d} \rfloor) \end{aligned}\)

又 \(\displaystyle g(1)S(n)=\sum_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\)

则\(\displaystyle g(1)S(n)=\sum\limits_{i=1}^{n}(f*g)(i)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\)

进行预处理\(\&\)数论分块即可

例题：P4213 杜教筛

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int N = 6e6 + 5;
typedef long long LL;
bool vis[N];
int t, cnt, mu[N], phi[N], prime[N], sum1[N];
LL n, sum2[N];
map<int, int> m1;
map<LL, LL> m2;
inline void prim(int x) {
	mu[1] = phi[1] = 1;
	for(int i = 2; i <= x; i ++) {
		if(vis[i] == 0) {
			prime[++ cnt] = i;
			mu[i] = -1, phi[i] = i - 1;
		}
		for(int j = 1; j <= cnt && i * prime[j] <= x; j ++) {
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else mu[i * prime[j]] = - mu[i], phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	for(int i = 1; i <= x; i ++) sum1[i] = sum1[i-1] + mu[i], sum2[i] = sum2[i-1] + phi[i];
}
int djsmu(int x) {
	if(x <= 6e6) return sum1[x];
	if(m1[x]) return m1[x];
	int ans = 1;
	for(int l = 2, r; l <= x; l = r + 1) {
		r = x/(x/l);
		ans -= (r - l + 1) * djsmu(x/l);
	}
	return m1[x] = ans;
}
LL djsphi(LL x) {
	if(x <= 6e6) return sum2[x];
	if(m2[x]) return m2[x];
	LL ans = x * (x + 1) / 2;
	for(int l = 2, r; l <= x; l = r + 1) {
		r = x/(x/l);
		ans -= (r - l + 1) * djsphi(x/l);
	}
	return m2[x] = ans;
}
int main() {
	scanf("%d", &t);
	prim(6000000);
	while(t --> 0) {
		scanf("%lld", &n);
		printf("%lld %d\n", djsphi(n), djsmu(n));
	}
	return 0;
}

Lagrange 插值

孙子定理

若\(m_1,m_2,\cdots,m_n\)是两两互质的正整数， \(M=\prod_{i=1}^n{m_i}\)，\(M_i=M/m_i\) , \(t_i\)是线性同余方程\(M_it_i\equiv 1 \ (mod \ m_i)\)的一个解

对于任意的n个整数\(a_1,a_2,\cdots,a_n\)，则同余方程组： \(\begin{cases}x≡a_1(mod\ m_1)\\x≡a_2(mod\ m_2)\\ \cdots \cdots\\x≡a_n(mod\ m_n)\\\end{cases}\) 有整数解

方程组的解为\(x=\sum_{i=1}^n M_it_i a_i\).并且在 \(\% \ M\) 意义下有唯一解。

证明

因为\(M_i=M/m_i\) 是除\(m_i\)之外所有模数的倍数，所以\(\forall \ k\not=i \ , \ M_it_ia_i\equiv 0 \ (mod \ m_k)\)

又因为\(M_it_ia_i\equiv a_i\ (mod \ m_i)\)
所以 \(x=\sum_{i=1}^n M_it_i a_i\)

结论

\(CRT\)给出了模数两两互质的线性同余方程组的一个特解。方程组的通解可以表示为 \(x+kM\ (k\in Z)\)。有些题目要求我们求出最小的非负整数解，只需把 \(x\) 对 \(M\) 取模，并让x落在 \([1,M)\) 内即可。

正文

对于一个多项式 \(f(x)\)，其图像在坐标系内经过 \(n\) 个点 \((x_i,y_i)\)

我们考虑对于此多项式的“孙子定理”：

构造 \(n\) 个多项式 \(g_i(n)\).对于第 \(i\) 个多项式，对于\(\forall k\not= i ，g_i(x_k)=0\)，而 \(g_i(x_i)=1\)，即 \(g_i(x_i)*y_i=y_i\)

则可得 \(g_i(x)=\frac{(x-x_1)(x-x_2)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n)}{(x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n)}\)

所以 \(\displaystyle f(x)=\sum_{i=1}^n g_i(x)*y_i\)

\(\mathcal{Code}\)：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL N = 2e3 + 5, mod = 998244353;
LL n, k, ans, x[N], y[N];
LL ksm(LL a, LL b) {
	int res = 1;
	for( ; b ;a = a * a % mod, b >>= 1) {
		if(b & 1) res = res * a % mod;
	}
	return res;
}
LL Lagrange(LL k) {
	LL ans = 0;
	for(int i = 1;i <= n;i ++) {
		LL res = 1;
		for(int j = 1;j <= n;j ++) {
			if(i == j) continue;
			res = (res * ((x[i] + mod - x[j])%mod)) % mod;
		}
		res = ksm(res, mod - 2);
		for(int j = 1;j <= n;j ++) {
			if(i == j) continue;
			res = (res * ((k + mod - x[j])%mod)) % mod;
		}
		res = res * y[i] % mod;
		ans = (ans + res) % mod;
	}
	return ans;
}
int main() {
	cin >> n >> k;
	for(int i = 1;i <= n;i ++) cin >> x[i] >> y[i];
	cout << Lagrange(k) << endl;
	return 0;
}

例题：P4781 拉格朗日插值