CSP 2019 集训 数学

数学

gcd

定义与证明

定义：$\gcd(a,b)$ 定义为最大的 $d$，使得 $d\mid a,d\mid b$。

$\gcd(a,b)=\gcd ( b,a \% b )$ 的证明：设 $a=bq+r$。

假设 $d\mid b$，则可以由上式证明 $d\mid a$ 等价于 $d\mid r$。证毕。

CQOI 2014 数三角形

用（简单）容斥原理，用三点组的个数减三点共线情况的个数。

如何计算三点共线情况的个数呢？

回忆这个定理：

定理 $2.33$ 设 $A(0,0),B(n,m)(n,m\in \mathbb{N}_{+})$，那么线段 $AB$ 上整点的个数即为$\gcd(n,m)+1$。（——能量采集）

只要暴力找出所有直线即可。

exgcd

算法证明

根据数论基础知识，$ax+by=\gcd(a,b)$（$a,b$ 是给定正整数，$x,y\in Z$）有无数组解。

并且，如果我们可以在欧几里得算法的过程中维护这个方程的解，那么就能在计算出 $\gcd$ 的同时把解也算出来。

首先，当 $b=0$ 时，这个方程的解就是 $(x,y)=(1,0)$。

接着，假设 $a=bq+r$，设 $bx'+ry'=g$，我们需要找出一组使得 $ax+by=g$ 的 $(x,y)$。

把 $a=bq+r$ 代入上面的式子得 $bqx+rx+by=g$，也就是 $b(qx+y)+rx=g$。把这个式子与 $bx'+ry'=g$ 比对即得 $qx+y=x',x=y'$，也就是 $(x,y)=(y',x'-qy')$。

青蛙的约会

随便推一下式子就可以得到 $t(n-m)+sL=x-y$，其中只有 $s,t$ 是整未知数。先把两边都除以 $\gcd(n-m,L)$，标准化之后用 $\mathrm{exgcd}$ 求解就行了。

小凯的遗憾 疑惑

证明起来似乎挺长的，还是要注重打表找规律。

快速幂 (kasumi) 与费马-欧拉定理

费马小定理

费马小定理：$p$ 是质数，那么 $\forall a\in [1,p),a^{p-1}\equiv 1\pmod{p}$。

当然可以用“元素的阶整除群的阶”证明。

这里提供一个使用二项式定理的证明方法。

$(a+1)^p=a^p+\mathrm{C}^1_pa^{p-1}+\mathrm{C}^2_pa^{p-2}+\cdots+\mathrm{C}^{p-1}_pa+1$。

由于 $p$ 是质数，因此 $\mathrm{C}^1_p,\mathrm{C}^2_p,\cdots,\mathrm{C}^{p-1}_{p}$ 的分母都没有 $p$ 因子，分子有 $p$ 因子，因此这些数都是 $p$ 的倍数。

因此 $(a+1)^p\equiv a^p+1$，从 $0^p\equiv 0$ 即可归纳出 $a^p\equiv a$。移项得 $a(a^{p-1}-1)\equiv 0$。由于 $a\in [1,p)$，因此两边除以 $a$（乘以 $a$ 的逆元）即得 $a^{p-1}\equiv 1$。

逆元

如何求逆元呢？可以用 $\mathrm{kasumi}$ 配合费马-欧拉定理，也可以用扩展欧几里得。

这里提供两种 $O(n)$ 线性推逆元的方法。

第一种是经典方法。设 $p=aq+r\ (0<r<a)$，那么 $aq\equiv -r$，$a^{-1}\equiv -qr^{-1}$。这种方法仅适用于 $p$ 是质数的情况。

第二种利用了阶乘。我们可以在 $O(n)$ 时间内计算出 $1!,2!,\cdots,n!$。接着我们用某一种方法计算出 $(n!)^{-1}$，并递推 $((n-1)!)^{-1}\equiv n\times (n!)^{-1}$。于是 $x^{-1}\equiv (x-1)!\times (x!)^{-1}$。这个方法也许比经典方法快，而且适用于 $p$ 不是质数的情况（但是 $n$ 必须小于 $p$ 的最小质因子）。而且由 $(n!)^{-1}$ 递推 $((n-1)!)^{-1}$ 的方法也可以用于分段打表计算阶乘的逆元。

计算系数 组合数问题

这两道题都涉及 $\mathrm{C}$ 的计算。可以灵活地运用定义式和杨辉三角递推式，在合适的场景使用合适的式子简化计算。也就是，如果 $n$ 只有 $2000$，那么使用杨辉三角就足够了。

中国剩余定理

如果 $p_1,p_2,\cdots,p_n$ 互质，那么下面方程组

$$\begin{cases}x \equiv a_1\pmod{p_1}\\\\ x\equiv a_2\pmod{p_2}\\\\ x\equiv a_3\pmod{p_3}\\\\ \vdots\\\\ x \equiv a_n \pmod{p_n}\end{cases}$$

在 $\mod{p_1 p_2 \cdots p_n}$ 意义下有唯一解。

如何求这一组解呢？

这里有一个神奇构造。

令 $M=\Pi p$，则 $M_i=\Pi^{i-1}_{j=1} p_j \times \Pi^{n}_{j=i+1} p_j$，于是 $t_i$ 是 $M_i$ 在 $\mod{p_i}$ 意义下的逆元。那么令 $x=\sum_{i=1}^n a_iM_it_i$ 即可。

如果考场上不记得神奇构造了，那就可以用 $\mathrm{exCRT}$。

主要应用还是合并同余方程。

各种筛

Violet 5 樱花

求不定方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 的正整数解数量。

令 $m=n!$。由于每一个 $x$ 唯一对应一个 $y$，因此我们可以把 $y$ 用 $x$ 表示，得到 $y=\frac{xm}{x-m}$。接着用分母换元法，令 $x-m=t$，$y=\frac{(m+t)m}{t}=\frac{m^2}{t}+m$。于是 $y$ 为整数的充要条件为 $t\mid m^2$。

同时，对 $m^2$ 的每一个因子 $t$，都可以唯一确定一组 $(x,y)$。因此只需要求 $m^2$ 的因子数，这只需要把 $n!$ 质因数分解就可以了。

因此对于这样的题目，进行必要的数论变换是非常重要的。

高精度

不要写错。

LLH邀请赛 大数计算器

求 $\mathrm{C}^r_n$ 的前 $3$ 位和去除所有末尾 $0$ 后的后 $9$ 位。

后 $9$ 位相当于模 $10^9$，直接用 泳装 一题的方法，把因子 $2$ 和因子 $5$ 分开处理即可。

前 $3$ 位怎么做呢？long double 信仰过？

太大了，连 long double 都会爆啊。

取一个 $\ln$ 然后相加减，最后 $\exp$ 吧。在对精度要求不高的时候，取对数也是不错的方法。

解方程

枚举是不是解的时候在模意义下进行，判断是不是真的解的时候用高精。

当然也可以凭信仰，选取几个模数，把所有系数也取模，在这几个模意义下都进行运算，如果都满足方程就“认为”这个数真的是解了。

容斥原理（经典型）

Cirno 的完美算数教室

暴力容斥，暴力出奇迹，记得加剪枝。

HAOI 2008 硬币购物

这个背包很有特点，物品种类很少，但是背包容量和物品数量很大，肯定不能 $\mathrm{dp}$ 或搜索。那么我们就用数学方法。

设第 $i$ 种硬币用了 $x_i$ 枚，那么 $c_1x_1+c_2x_2+c_3x_3+c_4x_4=s$，限制是 $0\le x_i\le d_i$。

假如没有限制，那么这题就是一个简单的隔板法，把定义域下界上调到 $1$ 就行了。

那么现在有了限制，就计算出各种“不符合限制”的情况，用容斥原理计算就行了。

具体地，用“总方案数”减去“至少某一种硬币不符合限制”的方案数，加上“至少某两种硬币不符合限制”的方案数，减去“至少某三种硬币不符合限制”的方案数，最后加上“四种硬币都不符合限制”的情况。

博弈论

取石子游戏 1 ——理解必胜和必败态

只有一堆石子，每次拿 $[1,k]$ 个，不能拿的输。

画状态图可以发现 $0,k+1,2(k+1),\cdots$ 都是先手必败，其余都是先手必胜。接下来归纳证明即可。

取石子游戏 2 ——组合游戏和 SG 函数

有 $n$ 堆石子，每次可以在一堆石子中拿任意多个，不能拿的输。

这个东西不用 SG 做实在不太行啊。

关于组合游戏和 SG 函数、SG 定理的理解，详见在学军的笔记。

Nim 是经典模型，$\mathrm{SG}(x)=x$。

如果针对 Nim 游戏，那么可以比较简单地对“异或方法”的可行性进行证明。

取异或值的最高位。由于这一位是最高位，因此一定存在一堆石子，它的石子数这一位为 $1$。令这一堆留下来的石子数恰好使得异或值为 $0$，那么留下来的石子数在那一位是 $0$，于是留下的石子数少于原来的石子数，也就是这种取的方案是一定可行的。

这样异或值非零一定能转移到异或值为零的状态。而异或值为零的状态只能转为异或值非零的状态，且终态异或值为零。于是证毕。

取石子游戏 3 ——游戏 1 和游戏 2 的结合

有 $n$ 堆石子，每次可以在 $[1,k]$ 堆石子中拿任意多个，不能拿的输。

考虑 $k=1$，那么就是游戏 2；若 $a_i=1$，那么就是游戏 1。因此这一个游戏是这两个游戏的结合。

又来一个神奇操作。把每一堆都用二进制表示，计算每一个二进制位