数论
https://codeforces.com/contest/1202/problem/B 题目大意 给出一个 $0 \sim 9$ 字符组成的序列 $S \ (1 \le |S| \le 2 \times 10^6)$ 且 $S$ 总以 $0$ 开始，这个序列是由 $x, y \ (0 \le x, y \le 9)$ 由以下规则生成出来的。 最初数字 $a$ 为 $0$。输出这个数 随机的从 $x, y$ 中选出一个数加到 $a$ 上并输出 $a$ 的个位
…
https://codeforces.com/contest/911/problem/C 题目大意 给出 $k_1, k_2, k_3 \ (1 \le k_i \le 1500)$，问是否可以选出一组整数 $x_1, x_2, x_3$ 使得对于任意 $x \ge \max(x_1, x_2, x_3)$ 有整数 $i, j$ 使得 $k_i * j + x_i$ 成立。 简要题解 这题乍一想只要 $k_i$ 都比较大，肯定是无解，但要枚举并证明小的数只有那么多
…
https://codeforces.com/contest/628/problem/B 题目大意 给出一个由 $0 \sim 9$ 字符组成的字符串 $S \ (|S| \le 3 \times 10^5)$。问其有多少个子串对应的数字可以被 $4$ 整除（允许前导零）。 简要题解 分为两种情况 $1$ 位，$2$ 位及以上。对于第二种情况只需要判断最后两位能被
…
https://codeforces.com/contest/1993/problem/C 题目大意 给定 $n$ 盏灯和 $n$ 长数组 $a_i (1 \le a_i \le 10^9)$ 和 $k$，$1 \le k \le n \le 2 \cdot 10^5$。 起初 $n$ 盏灯都不亮。$i$ 位置的灯在 $a_i$ 时刻第一次点亮，之后每过 $k$ 单位时间点亮熄灭状态反转一次。问最早什么时刻，所有灯都亮
…
扩展欧几里得算法（ExGCD） // ax+by=gcd(a,b)=g // check a>0 b>0 // if a != b, |x|<b, |y|<a template<typename T> void exgcd(T a,T b,T &g,T &x,T &y) { if(!b) { g=a; x=1; y=0; } else { exgcd(b,a%b,g,y,x); y-=a/b*x; } } 求逆元 template<typename T> void exgcd(T a,T b,T &g,T &x,T &y) { if(!b) { g=a; x=1; y=0; } else { exgcd(b,a%b,g,y,x); y-=a/b*x; } } template<typename T> T inv(T a,T m) { T g,x,y; exgcd(a,m,g,x,y); if(g!=1) return -1; // no inverse element if(x<0) x+=m; return x; } 不定方
…
扩展欧几里得算法 有时我们需要求解类似于 $ax+by=m$ 的不定方程（丢番图方程），扩展欧几里得算法就是求解这样方程的利器。 除此以外我们可以通过简单地变形处理模逆元和线性同余方程。 裴蜀定理/贝祖定理（Bezout&rs
…
最大公约数（GCD）与欧几里得算法 最大公约数（Greatest Common Divisor，GCD） 两个数最大公约数顾名思义，两个数的所有公约数中最大的。 若正整数 $a,b$ 的质因数分解为 $$a = \prod_{i} p_i ^ {e_{a,i}}$$ $$b = \prod_{i} p_i ^ {e_{b,i}}$$ 则其最大公
…
模下计算 普通 const int MO=1e9+7; inline int add(int x,int y) { x+=y; if(x>=MO) x-=MO; return x; } inline int sub(int x,int y) { x-=y; if(x<0) x+=MO; return x; } inline int mul(int x,int y) { return 1LL*x*y%MO; } inline void addv(int &x,int y) { x+=y; if(x>=MO) x-=MO; } inline void subv(int &x,int y) { x-=y; if(x<0) x+=MO; } inline void mulv(int &x,int y) { x=1LL*x*y%MO; } int qp(int x,int n) { int ans=1; while(n) { if(n&1) { mulv(ans,x); } mulv(x,x); n>>=1; } return ans; } ModInt template<int MO=1000000007> struct ModInt { int x; ModInt(int x=0):x(x){ norm();
…