数论基础
整除
对于两个整数 \(a\ ,\ b(a\neq 0)\) ，若 \(\exists k\in Z\) 使 \(ak=b\) 则称 \(a\) 整除 \(b\) ，记做 \(a|b\)
快速幂
快速幂用于快速计算 \(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\) 统计答案
| x | ans |
|---|---|
| \(x\) | \(x^{2^0}\) |
| \(x^2\) | \(x^{2^0}\) |
| \(x^4\) | \(x^{2^0}\) |
| \(x^8\) | \(x^{2^3}x^{2^0}\) |
| \(x^{16}\) | \(x^{2^3}x^{2^0}\) |
| \(x^{32}\) | \(x^{2^5}x^{2^3}x^{2^0}\) |
| \(x^{64}\) | \(x^{2^6}x^{2^5}x^{2^3}x^{2^0}\) |
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; }
扩展欧几里得算法
算法描述
用于求解关于 \(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; }
若我们已经知道以下的式子
\[bx_2 + (a\%b)y_2 = gcd(b, a \% b) \]则可以得出
\[ax_1 + by_1 = bx_2 + (a\%b)y_2 \] \[ax_1 + by_1 = bx_2 + (a - a / b * b)y_2 \] \[ax_1 + by_1 = ay_2 + b(x_2 - a/b*y_2) \]则有
\[x_1 = y_2,\ y_1 = x_2 - a / b * y_2 \]当 \(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\) 为最小正整数的一组解，可由以下公式推导
\[ax + by = 1 \] \[ax + by + k * ba - k * ba = 1 \] \[a(x + k*b) + b(y - k * a) = 1 \]则 \(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;
埃拉托色尼筛法
复杂度 $\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 拉格朗日插值