快速幂与取模

★ 而末行那句「有多少组的答案是 0」是「题面多问一句」的第八次 —— 这次它兜的是答案恰好为 0 的那些组（p = 1 和 a ≡ 0）， 也就是最容易被一句「顺手的特判」搞错的那一片。

2 10 1000000007            → 1024
-3 5 1000000007            → 999999764     ★ 负底数 + 奇次幂：(-3)⁵ = -243 ≡ p-243
5 0 1000000007             → 1             a⁰ = 1
0 0 7                      → 1             ★ 题面约定 0⁰ = 1
123456789 1000 1000000007  → 620139939
7 13 1                     → 0             ★ p = 1：任何数都 ≡ 0
999999937 12 999999999999999989 → 860406115710957185   ★ p ≈ 10¹⁸：乘法必须 __int128
5 0 1                      → 0             ★★ p = 1 且 b = 0 —— 这一组只有它抓得到 wrongOne
末行                        → 2             （答案是 0 的有两组）

⚠ 第二行值得单独看：(-3)⁵ = -243，而 C++ 里 -243 % (10⁹+7) 给的是 −243， 不是 999999764。少写一句 if (a < 0) a += p;，答案就是个负数。

⚠⚠ 而最后一组是专门为 wrongOne 加的： p = 1 那一行（第 6 组）它其实是对的 —— 因为 b = 13 ≥ 1，循环里 a = 7 % 1 = 0， res 乘着乘着就变 0 了。只有 p = 1 且 b = 0 同时成立，它才现形。 ★ 这件事第 9 步会变成整整一档生成器。

点「运行 ▶」看结果

b = 10¹⁸（二进制 60 位，其中 24 个 1）、p ≈ 10¹⁸（二进制 60 位）：

★★ 那个 84 是这么来的，而且是个等号：

乘法次数 = popcount(b)（乘进答案的次数）+ 二进制位数（平方的次数）= 24 + 60 = 84。 （和第 38 章树状数组那个「步数恰好等于 popcount(r)」是同一种数法。）

⚠ 而这张表里有一件很容易被忽略的事： 快速幂的乘法次数只和 b 有关，和 p 一点关系都没有； 只有龟速乘那一行跟着 p 走（每次乘法换成 ⌊log₂p⌋+1 次加法）。

★ 两条曲线的旋钮根本不是同一个 —— 下一步那张耗时表会把这件事量出来。

递归的说法（接第 12 章的分治）：

• b 是偶数：a^b = (a^(b/2))²
• b 是奇数：a^b = a · (a^((b−1)/2))²

⇒ 每一步把指数砍一半，所以只要 ⌊log₂b⌋ + 1 步。

迭代的说法（更好记，也是代码里那五行）—— 把 b 看成二进制：

b = 13 = 1101₂   ⇒   a¹³ = a⁸ · a⁴ · a¹

于是「从低位往高位扫 b，位是 1 就把当前的 a^(2^k) 乘进答案」：

ll res = 1 % p;
while (b) {
    if (b & 1) res = (i128)res * a % p;
    a = (i128)a * a % p;
    b >>= 1;
}

★ 这两种说法的次数是同一个：popcount(b) 次「乘进答案」+ 位数次「平方」。

★★ 最后两条要的是「两个边界同时出现」—— 这是前十五章都没碰到过的形状。

① 「成对造」把最弱支从 46 抬到 111（One 66 → 185、Zero 46 → 111）。

道理很简单，算一下就明白：把两个边界各自独立地塞进去， b = 0 的概率是 20%、a ≡ 0 的概率是 15% —— 同时发生只有 3%，一组询问平均 5.5 条，也就是每轮 15% 左右。 而「成对造」直接把这两件事绑在一起发生。

★★★ 有些 bug 要的不是「某一个特定的值」（第 41 章那条）， 而是「两个特定的值同时出现」—— 靠各自独立的概率相乘，等一辈子也等不来。

② 两个对照档说明另外两处也不可替代： 撤掉「p 塞 1」→ wrongOne 回到 0；撤掉「p 到 10¹⁸」→ wrongOverflow 回到 0。

③ ⚠ 而「成对造」是有代价的：Loop / Order / Neg / Ovf 四列各掉 10 上下 （287 → 278、136 → 125……），因为四分之一的询问被「b = 0」占掉了，那些询问测不到别的。

★ 又是第 30 章那条：把 0 变成非 0，掉多少抓获率都划算。