Posts

在算法竞赛中，很多赛题都需要输出一整个数组，但是由于评测姬的机制不同，某些OJ会卡行末空格，这样的体验是很痛苦的，如果不报PE那更是要命。 在众多避免行末空格的方法中，cout << "\n "[i < n];显得十分简洁，但是它究竟是什么语法允许的？之前一直想不通，今天突然想到了下标，测试了一下果真如此，同时也找到了具体的语法依赖。 先上结论：其实就是下标 详情见下图实例： 那么，当[i < n]为真，"\n "[1]为' '； 反之为"\n "[0]，即'\n'。 这样，在数组最后一个元素输出后，输出的就不是空格，而是换行。 具体过程 Water 以前在大佬们（第一次好像是在逆十字的代码里看到的）的代码中总是看见这种避免行末空格的写法，但是并不知道这是什么语法（但是好用）。 开始以为是c++11开始的lambda表达式，但是我找文档啃了半天也找不到对应实例。然后今天终于开窍了。（误，其实答案早就找到了，倒是没太仔细求证给忽视了） 在微软的文档中写的为postfix表达式，即后缀表达式。 它其实说明了一个问题，这个"\n "和一个普通的数组一样。也就是说，这个语句在编译器中就和cout << s[i];一样自然。 当然，如果你知道"abcd"的类型实际是const char *，后面下标运算符其实带来的结果就是对指针的加减，那么，这种写法已不构成理解问题。 其他发现 下标运算符 下标运算符是可交换的。 因此，只要下标运算符未重载，表达式 array[index] 和 index[array] 就是等效的。 第一种形式是最常见的编码做法，但它们都有效。 事实上，下面的代码也能得到一致的结果。 1 2 3 for (int i = 0; i < 4; i++) { cout << (i)["abcd"] << ' '; } 参考链接 Docs Microsoft C++、C 和 汇编程序 C++ 语言 C++ 语言参考 内置运算符、优先级和关联性 下标运算符： 摘录一下我们需要的依赖项： ...

闲言 比赛链接：传送门 没有代码，放心食用。 A Find Subsequence （WA了一晚上，回来把树状数组重写了一下就过了？？？） 树状数组 + DP 令dp[i]表示前$i$个元素中，以a[i]结尾的只出现一次的子序列的数目。 a[i]在之前未出现过： $$dp[i]=1+\sum_{k=1}^{i-1}dp[k]$$ a[i]在之前出现过，考虑上一次出现的位置。显然当前位置使得上一次出现的位置之前的贡献变成$0$，同时处在区间$[last[a_i], i-1]$的贡献不改变。 $$dp[i]=\sum_{k=last[a_i]}^{i-1}dp[k]$$ dp[last[a[i]]]将变成0。 B operation ((a & b) + (a | b)) >> 1等价于(a + b) >> 1 最后一次合并可以等价为，将数组从中划分成两半，分别操作完后再合并 由于可能的答案很少，考虑枚举分割点记忆化搜索。 C 翻墙之旅 10.2组队训练有一样的题：Gym 103306A Alice Birthday SoSDP 令所有点构成的点集为$sn$，考虑一个包含点1的点集$s$，令f[s]表示使得$s$中只有一个连通分量的（点集内部的）删边方案数，cnt[s]表示点集$s$内的边数。在$s$中，点1一定能到达连通分量内的所有点，且此时外部的所有的边都可以选择删或者不删，那么该状态对$s$内的所有点的贡献即为$2^{cnt[sn-s]}\times f[s]$。 cnt[s]的计算不再赘述，关键讲f[s]： $s$内所有边的存在形式有$2^{cnt[s]}$种，减去有多个连通分量的情况即为只有一个连通分量的数目， $$2^{cnt[s]}-\sum_{s_0 \subset s} f[s_0]\times 2^{cnt[s-s_0]}$$ 使用SoSDP（子集DP）计算，为了避免重复计算，可以限定$s_0$中包含$s$的lowbit，或者其它的某点。 1 2 3 for (int s = 0; s < bit[n]; s++) for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s) if (s0 & (s & -s)) ... D SumMin 如果你了解Floyd枚举的各个变量的含义，这就是个裸题。 1 2 3 for (int k = 1; k <= n; k++) // 中间点集合 for (int i = 1; i <= n; i++) // 起点 for (int j = 1; j <= n; j++) // 终点 删点顺序逆过来便是枚举中间点集合的顺序。 ...

一直没啥想写的，不过最近又看见一道和欧拉示性数公式相关的思维题，所以萌生出了写这篇博客的想法。 首先是关于平面图欧拉示性数公式的定义： 设$G$是一个连通的平面图，顶点的数目为$V$，边的数目为$E$，面的数目为$F$，则有$$V+F-E=2$$ 下面使用数学归纳法进行证明： 当$E=0$时，有$V=1,F=1$，等式显然成立。 假设当$E=k$时等式成立，下面考虑$E=k+1$的情形。 当图中无环时易知$V=k+2,F=1$，等式显然成立。 反之，我们设$e$为环中的一条边，那么对于图$G\setminus\set{e}$由假定知等式成立（即为$E=k$的情形，令其$V=v_0,F=f_0$，则$v_0+k-f_0=2$）。那么对于图$G$我们有$V=v_0,E=k+1,F=f_0+1$，因此等式也成立。 综上，由数学归纳法可知等式对于$E\geq0$的情形皆成立。 具体使用 声明 下面这种方法只在本人太闲了弄出来玩的，实际体验并不一定好。 简单来说就是固定了边数，在使点数尽可能小，从而使之面的数目最大化。 CSUST OJ 1066 被打脸的潇洒哥 题目描述 平面上有n个圆，求使这n个圆两两相交（即每两个圆之间恰好有两个交点）后最多能把平面划分成多少个区域。 对于圆这样的图形，我们不方便计算它的各项参数，可以直接将其边无限细分，即假定点数为$m$，则边也为$m$。由于$m$无穷大，两圆相交时并不会产生新的边，但是会减去重叠的两个点。 所以，当一共有$n$个圆时，图上的各项参数为 $$E=n\times m,V=n\times m-2\times {n \choose 2},F=2+E-V=2+n\times(n-1)$$ 1 2 3 4 5 6 7 8 9 int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); for (cin >> T; T--; ) { cin >> n; if (n == 0) {cout << 1 << '\n'; continue;} cout << 2 + (n - 1) * n << '\n'; } return 0; } HDU 2050 折线分割平面 我觉得不需要题目描述了，标题即描述。 由于折线比较特殊，不方便定义端点，我们可以先直接划定边界，例如放一个圆$V=n_0,E=n_0$，但此时圆外的区域不能算作一块平面。同时，折线就可以改成两条共端点的线段。 然后就按常规的来，无穷细分一条线段为$V=k,E=k-1$。则当共有$n$条折线时，图的各项参数（使$F$最大的情况，由于边数确定即交点尽可能多）为 $$E=n_0+n\times2(k-1),V=n_0+n\times(2k-1)-2n-4\times{n \choose 2}$$ 所以$F=1+E-V=1+n+2n(n-1)$ 1 2 3 4 5 6 7 8 int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); for (cin >> T; T--; ) { cin >> n; cout << 1 + n + 2 * n * (n - 1) << '\n'; } return 0; }

比赛链接 （ps: 写题请到Problems页面） 可能算详解？代码部分随缘写。 题解 A. NO GAMES NO LIFE 题目描述 共有$n$（偶数）堆棋子，第$i$堆初始为$1 \leq a_i \leq 100$，玩家每次必须选$\frac{n}{2}$堆棋子并使之减少正整数个，每次每堆减少的值可以不同。 Bai先手，Kong后手。玩家无法选择时失败。 基准思路： 谁先导致场上出现被取完的堆必定输掉游戏 如果选了1则必须减少到0 考虑数字1的数量，令$cnt[i]$为数字$i$的个数。 $cnt[1] > \frac{n}{2}$时玩家必选到1，必输 $1 \leq cnt[1] \leq \frac{n}{2}$可以增加1的数量使下家面临第一个局面，必胜 $cnt[1] = 0$时考虑2的数量 $cnt[2] > \frac{n}{2}$玩家必选到2，必然产生1，且个数不大于$\frac{n}{2}$，必输 $1 \leq cnt[2] \leq \frac{n}{2}$可以增加2的数量使下家面临上一个局面，必胜 $cnt[2] = 0$时考虑3的数量 $\dots$ 显然，问题只与最小值的数量有关。 B. 整除数 题目描述 找到最小的$n$位能被$m$整除的自然数 $n=1$时，直接输出0 找到最小的$n$位整数$10^{n-1}$，求最少还需多少使得其能被$m$整除，即$(m - 10^{n-1} % m) \mod m$，如果加上后位数不变则为答案，否则无解。 C. 网格图 题目描述 从$(0,0)$，每次你只可以往正东走，或者往正北走(即x，y坐标增大的方向)。但是你每次走的长度可以是任意正实数。这个网格上有$\mathit n$个景点，你可以经过任意个景点，问：以每个景点为终点时，分别能走出多少条不同路线。(当且仅当经过的景点不同时才被视为不同路线) 取模$1e9+7$. 由于是走正实数，某点左下方的所有景点都可以直接到达该点。 比较特殊的是与之处在同一行列的点，这里就只需加上到最近的那个点的方案数。 思路，按照$(x,y)$从小到大排序，只要保证到某点时，所有处于其左下方的点都已经更新答案，那么该点的方案就是它们求和再+1（从$(0,0)$直达）。 同时要维护行列点数目，每次更新答案后再更新即可。 ...

很抱歉的是，关于吉老师线段树历史最值问题本文尚并未涉及。 （开个新坑） 只是最近写题时觉得它让我对线段树的使用有了新的理解，故做记录。 我的理解 吉老师线段树不同于朴素线段树的地方在其维护方式，在维护区间最大（小）值的同时维护了严格次大（小）值。 这使其对某些问题有着几近玄学的复杂度。。。 一部分使用标记，另一部分使用暴力修改，单次修改变成了$O(\log^2 n)$。 初次看到时，我是真的无法接受，并且将其作为假算法略过了（顺带一提，我当时在写下面贴的模板题时考虑维护最大，最小值TLE了） 然后上次ccpc压力测试赛上又碰见了Lowbit，写的时候突然发觉这其实是个很朴素的想法，一部分考虑暴力从而减少整体的复杂度（算是均摊？）。 线段树维护值时怎么就不能用呢？ 题目 HDU5306 Gorgeous Sequence 题目描述 x y t: For every $x≤i≤y$, we use min(ai,t) to replace the original ai’s value. x y: Print the maximum value of ai that $x≤i≤y$. x y: Print the sum of ai that $x≤i≤y$. 知道思路后，题目就太板子了，懒得重写了（将就看，不会真有人看吧，不会吧，不会吧） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 #include <cstdio> typedef long long i64; #define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++) #define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; }) #define pc(x) (p - puf == 1 << 20 ? (fwrite(puf, 1, 1 << 20, stdout), p = puf) : 0, *p++ = x) #define print(x, b) ({ pt(x), pc(b); }) char buf[1 << 20], *p1, *p2, puf[1 << 20], *p = puf; int pt(i64 x) { return x <= 9 ? pc(x + '0') : (pt(x / 10), pc(x % 10 + '0')); } const int N = 1e6 + 10; int T; inline void down(int s, int t, int nd); inline i64 min(i64 a, i64 b) { return a < b ? a : b; } inline i64 max(i64 a, i64 b) { return a > b ? a : b; } inline void swap(int & a, int & b) { a ^= b ^= a ^= b; } #define ld nd << 1 #define rd nd << 1 | 1 struct node { i64 mx, sm, lz, mxx, num; void set(i64 x) { sm = mx = x, num = 1, mxx = -1; } } tr[N << 2]; inline void merge(int nd) { int l = ld, r = rd; tr[nd].sm = tr[l].sm + tr[r].sm; if (tr[l].mx == tr[r].mx) { tr[nd].mx = tr[l].mx, tr[nd].num = tr[l].num + tr[r].num; tr[nd].mxx = max(tr[l].mxx, tr[r].mxx); } else { if (tr[l].mx < tr[r].mx) swap(l, r); tr[nd].mx = tr[l].mx, tr[nd].num = tr[l].num; tr[nd].mxx = max(tr[r].mx, tr[l].mxx); } } inline void build(int s, int t, int nd) { tr[nd].lz = -1; if (s == t) { tr[nd].set( read() ); return; } int m = s + t >> 1; build(s, m, ld), build(m + 1, t, rd), merge(nd); } inline void pushlz(int s, int t, int nd, i64 v) { if (~tr[nd].lz && tr[nd].lz <= v) return ; if (tr[nd].mx <= v) return ; tr[nd].lz = v; if (tr[nd].mxx < v) { tr[nd].sm -= tr[nd].num * (tr[nd].mx - v), tr[nd].mx = v; } else down(s, t, nd), merge(nd); } inline void down(int s, int t, int nd) { int m = s + t >> 1; pushlz(s, m, ld, tr[nd].lz), pushlz(m + 1, t, rd, tr[nd].lz); tr[nd].lz = -1; } inline void update(int s, int t, int nd, i64 v, int R, int L) { if (R < s || t < L) return ; if (L <= s && t <= R) return pushlz(s, t, nd, v); if (~tr[nd].lz) down(s, t, nd); int m = s + t >> 1; if (L <= m) update(s, m, ld, v, R, L); if (R > m) update(m + 1, t, rd, v, R, L); merge(nd); } inline i64 S(int s, int t, int nd, int R, int L) { if (L <= s && t <= R) return tr[nd].sm; if (~tr[nd].lz) down(s, t, nd); int m = s + t >> 1; i64 res = 0; if (L <= m) res += S(s, m, ld, R, L); if (R > m) res += S(m + 1, t, rd, R, L); return res; } inline i64 M(int s, int t, int nd, int R, int L) { if (L <= s && t <= R) return tr[nd].mx; if (~tr[nd].lz) down(s, t, nd); int m = s + t >> 1; i64 res = 0LL; if (L <= m) res = max(res, M(s, m, ld, R, L)); if (R > m) res = max(res, M(m + 1, t, rd, R, L)); return res; } int main() { T = read(); while (T--) { int n = read(), q = read(); build(1, n, 1); while (q--) { switch (read()) { case 0: update(1, n, 1, read(), read(), read()); break; case 1: print(M(1, n, 1, read(), read()), '\n'); break; case 2: print(S(1, n, 1, read(), read()), '\n'); break; } } } fwrite(puf, 1, p - puf, stdout); return 0; } HDU7116 Lowbit ...

$\text{Baby Step/Giant Step Algorithm}$ 用于解决这样一类同余方程的方法 $$a^x \equiv b\pmod c$$ 结合原根的知识还能解决模数有原根的$N$次剩余问题 $$x^n \equiv b\pmod c$$ 基础问题 $a^x\equiv b\pmod c$ 具体来说，BSGS的思路就是分块预处理+hash。 下面分情况讨论： Case gcd(a,c) == 1 由欧拉定理可知$x$的取值范围不会大于$\varphi(c)$，我们直接取$x<c$即可。 $a,c$互素时，存在$a$在模$c$意义下的逆元。 令分块的大小为$\lceil\sqrt c\rceil$，即我们将解的形式限定为$x=A\times\lceil\sqrt c\rceil - B,A,B\in[0,\lceil\sqrt c\rceil]$，直接将$a^B$的部分放到同余式右侧。 现在需要解决的问题变成： $$a^{A\times\lceil\sqrt c\rceil}\equiv b\times a^{B}\pmod c$$ 首先预处理，枚举$b\times a^B$的取值，并将其存下来(hash) 枚举$A$的取值，并查看是否存在对应的$B$是得两侧相等。 得到结果，或者无解。 Case gcd(a,c) != 1 一个比较好的想法是，我们将其转换成互素的情况。 由于$ax\equiv b\pmod c, g=\gcd(a, b, c)$可以转化成 $$\frac{a}{g}x\equiv \frac{b}{g}\pmod{\frac{c}{g}}$$ 同样的，我们也可以不断去消去$c$中与$a$不互素的部分，从而达到目的 具体步骤为： $a\times a^{x-1}\equiv b\pmod c$ $g=(a,c)$，若$g\nmid b$则无解 $\frac{a}{g}\times a^{x-1}\equiv \frac{b}{g}\pmod{\frac{c}{g}}$ 循环操作直到$(a,c)=1$或$\frac{a^k}{G}=\frac{b}{G}$ 代码模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 ll qpow(ll x, ll n, ll mod) { ll res = 1LL; for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) { if (n & 1LL) res = res * x % mod; } return (res + mod) % mod; } // a^x EQUIV n (MOD mod), and gcd(a, mod) = 1 ll BSGS(ll a, ll n, ll mod) { a %= mod, n %= mod; if (n == 1LL || mod == 1LL) return 0LL; unordered_map<ll, ll> bs; ll S = sqrt(mod) + 1; ll base = n; for (ll k = 0, val = base; k <= S; k++) { bs[val] = k, val = val * a % mod; } base = qpow(a, S, mod); for (ll x = 1, val = base; x <= S; x++) { if (bs.count(val)) return x * S - bs[val]; val = val * base % mod; } return -1; // No solution } pair<ll, ll> exgcd(ll a, ll b) { bool neg_a = (a < 0), neg_b = (b < 0); ll x = 1, y = 0, r = 0, s = 1; while (b != 0LL) { ll t = a / b; r ^= x ^= r ^= x -= t * r; s ^= y ^= s ^= y -= t * s; b ^= a ^= b ^= a %= b; } return {neg_a ? -x : x, neg_b ? -y : y}; } ll inv(ll a, ll mod) { auto [res, _] = exgcd(a, mod); return (res % mod + mod) % mod; } // a^x EQUIV n (MOD mod), and gcd(a, mod) != 1 ll exBSGS(ll a, ll n, ll mod) { a %= mod, n %= mod; if (n == 1LL || mod == 1LL) return 0LL; ll k = 0, val = 1; for (ll g = __gcd(a, mod); g != 1LL; g = __gcd(a, mod)) { if (n % g != 0LL) return -1; // No solution mod /= g, n /= g; val = val * (a / g) % mod, k++; if (val == n) return k; } ll res = BSGS(a, n * inv(val, mod) % mod, mod); return ~res ? res + k : res; } $N$次剩余问题（离散对数） 要求模数要有原根，令为$g$。 ...

随机数据下十分优秀的处理区间赋值操作的暴力数据结构。 本篇只给出split和assgin操作的代码，其它更暴力的就不提了，一般的能用的情况下有这两个应该就够了。 基础操作 思路十分清晰简单（暴力），维护一个有序的区间段的集合，每段区间带上其属性。 拆分前用lower_bound找到对应的位置，删去中间原来所有的后，再加入新的那段。 注意，set.erase(begin, end)为前闭后开，所以在找右端点时应该找R + 1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 struct ODT { map<ll, ll> mp; ODT(ll _, ll unit) { mp[_ - 1] = unit; } void split(ll x) { mp[x] = prev(mp.upper_bound(x))->se; } void assign(ll l, ll r, ll v) { split(l), split(r + 1); auto it = mp.find(l); while (it->fi != r + 1) it = mp.erase(it); mp[l] = v; } ll query(ll l, ll r) { split(l), split(r + 1); auto it = mp.find(l); ll res = 0; while (it->fi != r + 1) { auto nex = next(it); res += it->se * (nex->fi - it->fi); it = nex; } return res; } }; 例题 CF915 E. Physical Education Lessons 多次区间赋值（全变成0或1），再加上求总和。 ...

对于二次剩余式 $$x^2\equiv n\pmod p$$ 其中$p$为奇素数，且$p \nmid n$，求$x$。 Cipolla算法 $Cipolla$和之前就写过的三次剩余是同一个思路，所以我在写完$Cipolla$后感觉好像什么都没变。 构造一个环 $$R=\frac{\mathbb{Z}_p[x]}{x^2-a}=\set{\alpha+\beta Y | \alpha,\beta,\in\mathbb{Z}_p,Y^2=a}$$ 可知， 对于$z\in R$，即$z=\alpha+\beta Y$，有$z^{p-1}\equiv 1\pmod{p}$ 如果$z^{\frac{p-1}{2}}=\beta_0 Y$，则有$(\beta_0 Y)^2\equiv\beta_0^2a\equiv1\pmod{p}$，即$\sqrt{a}\equiv\beta_0^{-1}\pmod{p}$ 代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 mt19937 rng(__builtin_ia32_rdtsc()); inline ll randint(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } ll qpow(ll x, ll n, ll mod) { ll res = 1LL; for (x %= mod; n > 0LL; n >>= 1, x = x * x % mod) { if (n & 1LL) res = res * x % mod; } return (res + mod) % mod; } struct R { ll a, p, x, y; R(ll _a, ll _p) : a(_a), p(_p) { x = 1LL, y = 0LL; } void rand() { x = randint(0, p - 1); y = randint(0, p - 1); } R &operator*=(const R &rhs) { ll _x = (x * rhs.x + y * rhs.y % p * a) % p; ll _y = (x * rhs.y + y * rhs.x) % p; x = _x, y = _y; return *this; } void pow(ll n) { R res(a, p), b = *this; for (; n; n >>= 1, b *= b) { if (n & 1LL) res *= b; } x = res.x, y = res.y; } }; ll Cipolla(ll a, ll p) { a = (a % p + p) % p; if (a == 0) return 0LL; if (qpow(a, (p - 1) / 2, p) != 1LL) return -1LL; // No Solution if (p % 4 == 3) return qpow(a, (p + 1) / 4, p); R t(a, p); while (true) { t.rand(), t.pow((p - 1) / 2); if (t.x == 0 && t.y != 0) { return qpow(t.y, p - 2, p); } } assert(false); return -1; } Tonelli-Shanks算法 (来自柯召的《初等数论》) ...

$\forall a<m,(a, m)=1$，均有$a^{\varphi(m)}\equiv1\pmod{m}$，于是就有欧拉定理： $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况（比如$10^{30000}\mod 13$），欧拉降幂的作用不可忽视，但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广，读者大抵早已熟记于心，这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本，即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ 证明 - 欧拉定理 证明方法来自《初等数论》柯召 考虑这样一组数$r_1,r_2,\dots,r_{\varphi(m)}$，满足$\forall r_i\in \set{r_1,r_2,\dots,r_{\varphi(m)}},\mathrm{s.t.}(r_i,m)=1$，同时$\forall i\ne j,(r_i,r_j)=1$。 当$(a,m)=1$，我们可以得到: $$ \begin{aligned} (ar_1)(ar_2)\dots(ar_{\varphi(m)}) & \equiv & r_1r_2\dots r_{\varphi(m)}\pmod{m}\newline (r_1r_2\dots r_{\varphi(m)})\times (a^{\varphi(m)} - 1) & \equiv & 0\pmod{m} \end{aligned} $$ 由于$(r_i,m)=1$，可知$(r_1r_2\dots r_{\varphi(m)},m)=1$，故$a^{\varphi(m)}\equiv1\pmod{m}$。 拓展情况 这里的讨论是基于$(a,m)\ne1$的情况来的，因为当$(a,m)=1$成立时直接用欧拉定理就能推知上式成立。 由于$n=\lfloor\frac{n}{\varphi(m)}\rfloor\times\varphi(m) + \langle n \rangle_{\varphi(m)}\geq\varphi(m)$，不妨令$n=\lambda\varphi(m) + \langle n\rangle_{\varphi(m)},\lambda\in\mathbb{Z}^+$。 问题转换为证明$a^{\lambda\varphi(m)}\equiv a^{\varphi(m)}\pmod m$，这可以从$\lambda=2$的情况递推过去，下面证明$\lambda=2$时同余式成立。 将$a$因式分解，其中与$m$互素的部分可以直接使用欧拉定理消去，剩余的素数幂乘积分开后的情况和原问题同一结构，所以只考虑单个素数情况即可。原问题等价为证明：$p^{2\times\varphi(m)}\equiv p^{\varphi(m)}\pmod m,p\in Prime$。 ...

题外话：好像文章有点长，本地调的时候加载目录都掉帧了。虽然一度想删点题目，但思前想后还是一题没删，总感觉每一题都代表了一种典型，实在不好取舍，或许只写推导会好一点，但还是有点怕代码的实现未有较好交代。。。 好了，闲言少叙。 本篇是平时刷的反演题目的解题记录，个人认为这方面的知识点和写题目是有点脱节的，题目要么是纯套路，要么就是有些不太友好的小技巧。 题目来源：Luogu, LibreOJ, HDU等。 P3312 [SDOI2014]数表 题目描述 有一张 $n\times m$ 的数表，其第 $i$行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。 输入包含多组数据。 输入的第一行一个整数 $Q$ 表示测试点内的数据组数 接下来 $Q$ 行，每行三个整数 $n$，$m$，$a$（$|a|\le 10^9$）描述一组数据。 答案模$2^{31}$。 显然有答案为： $$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))[\gcd(i,j)\leq a] \newline$$ 先不考虑大小限制，之后将其转换成离线求值+动态加入贡献的问题。 $$ \begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{m}\sigma(\gcd(i,j))&=\sum_{d=1}^{n}\sigma(d)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}[\gcd(i,j)=1]\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)\sum_{i=1}^{[\frac{n}{d}]}\sum_{j=1}^{[\frac{m}{d}]}\newline &=\sum_{d=1}^{n}\sigma(d)\sum_{k=1}^{[\frac{n}{d}]}\mu(k)[\frac{n}{dk}]\times[\frac{m}{dk}]\newline &=\sum_{T=1}^{n}[\frac{n}{T}][\frac{m}{T}]\sum_{d\mid T}\sigma(d)\mu(\frac{T}{d}) \end{aligned} $$ 只有当$\sigma(n)\leq a_i$，才将$\sigma(n)$的贡献计入，那么我们可以离线处理，用树状数组维护，$O(Q\sqrt{n}\log{n})$。 取模$2^{31}$标志着需要$32$位整型自然溢出，当然最终还是要变成无符号整数，这里可以写成ans & 2^{31}-1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include <bits/stdc++.h> #define PII pair<int, int> #define fi first #define se second using namespace std; typedef long long i64; const int N = 1e5; const int mod = 0x7fffffff; int T; struct Query { int n, m, a, id; bool operator < (const Query &b) const { return a < b.a; } } Q[N + 10]; int ans[N + 10]; PII s[N + 10]; int mu[N + 10]; bitset<N + 10> ok; int pr[N], cnt; int sig[N + 10], pw[N + 10]; void init(int n) { mu[1] = sig[1] = 1; for (int i = 2; i <= n; i++) { if (!ok[i]) mu[pr[++cnt] = i] = -1, sig[i] = i + 1, pw[i] = i; for (int j = 1; j <= cnt && pr[j] <= n / i; ++j) { int t = pr[j] * i; ok[t] = 1; if (i % pr[j] == 0) { pw[t] = pw[i] * pr[j]; sig[t] = 1LL * sig[i] * (pw[t] * pr[j] - 1) / (pw[t] - 1); break; } mu[t] = -mu[i], sig[t] = sig[i] * (pr[j] + 1), pw[t] = pr[j]; } } for (int i = 1; i <= n; i++) s[i].fi = sig[i], s[i].se = i; sort(s + 1, s + 1 + n); } int tr[N + 10]; inline void ins(int p, int v) { for (; p <= N; p += p & -p) tr[p] += v; } inline int que(int p, int r = 0) { for (; p; p &= p - 1) r += tr[p]; return r; } inline int slove(int n, int m, int res = 0) { if (n > m) n ^= m ^= n ^= m; for (int l = 1, r; l <= n; l = r + 1) { int fn = n / l, fm = m / l; r = min(n / fn, m / fm); res += fn * fm * (que(r) - que(l-1)); } return res; } int main() { init(N); scanf("%d", &T); for (int i = 1; i <= T; i++) scanf("%d%d%d", &Q[i].n, &Q[i].m, &Q[i].a), Q[i].id = i; sort(Q + 1, Q + 1 + T); for (int o = 1, k = 1; o <= T; o++) { while (k <= N && s[k].fi <= Q[o].a) { for (int d = s[k].se, sg = s[k].fi, i = d, t = 1; i <= N; i += d, ++t) ins(i, sg * mu[t]); k++; } ans[Q[o].id] = slove(Q[o].n, Q[o].m); } for (int i = 1; i <= T; i++) printf("%d\n", ans[i] & mod); return 0; } P3172 [CQOI2015]选数 题目大意 ...