简单版高精度 #include <bits/stdc++.h> using namespace std; struct bigint { int d[1000]; int len; bigint() : len(0) { memset(d, 0, sizeof(d)); } void fix() { while (len >= 2…

快速读入 int read() { int f=1,x=0;char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1…

STL vector 构造函数 vector<int> a(5); // {0, 0, 0, 0, 0} vector<int> b(5, 3); // {3, 3, 3, 3, 3} int arr[5] = {0, 3, 2, 4, 1} vector<int> c(arr + 1, arr + 5); //…

手写哈希表 // 用法和 unorder_map 一样（除了 tb[k]=p 改成 tb.add(k,p)） // 支持 a = tb[tmp] 的用法 #define HASHMOD 233333 #define HASHSIZE 1000000 static struct HashTable { int head[HASHMOD]; int k…

最大公约数 欧几里得算法 int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } 扩展欧几里得算法 求 $ax+by=c$ 的解以及逆元（$a,b,c>0,c=gcd(a,b)$） // 返回 d=gcd(a,b); 和对应于等式 ax+by=d 中的 x,y; int exgcd(…

线性筛素数 int prime[N], num[N], tot; void init() { for(int i = 2; i < N; i++) { if(!num[i]) { prime[++tot] = i; } for(int j = 1, x; j <= tot && (x = i * prime[j]) &l…

中国剩余定理 tips 对于模数不为质数的问题进行求解，我们可以将其因式分解为几个互质的数 (例：$1e9=5^9\times 2^9$)，分别在小模数下应用某些技巧求解 (例：卢卡斯定理，暴力等)，最后通过 CRT 合并答案。 O(1)快速乘 用于解决中间过程的乘法超出 $2^{64}$ 范围。 inline ll mul(ll x, ll y,…

二次剩余 洛谷P5491 【模板】二次剩余 题目大意 求 $x^2\equiv N\pmod p$ 的解。 typedef long long ll; typedef pair<ll, ll> pll; #define mp make_pair namespace Complex { ll mod, W, W0; struct comp…

重要引理 $$ \left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\right\rfloor $$ 数论分块 洛谷P1403 题目大意： 设$f(x)$为$x$的约数个数，求$\sum_{i=1}^{n}f(i)$ 分析： 枚举约…

较简单的容斥 XMU区域赛选拔D 塔子哥数数 题目大意： 设 $g(x)$ 为莫比乌斯函数的绝对值，把 $g(1)g(2)g(3)...g(n)$ 连起来看成一个10进制数，其中 $g(1)$ 是最高位，那么这个数是多少。 解题思路： 正难则反，我们可以先考虑所有位是 $1$ ，再刨除 $g(i)=0$ 的位置。 计算所有位是 $1$ 的$n$位数…