洛谷 P1226 【模板】快速幂

// P1226 【模板】快速幂 —— 能 AC 的那一版
//
// 算法本身第 42 章从头讲到尾了，这一页只做一件事：
// **把第 42 章列的六个错法，逐个代进这道题的数据范围，看哪些还能发生。**
//
// 题面的范围：0 <= a, b < 2³¹，a + b > 0，2 <= p < 2³¹。
// 三处直接决定了写法：
//   ① **a >= 0** ⇒ 第 42 章那句「负数要归一化」在这道题上一次都用不上；
//   ② **p >= 2** ⇒ `1 % p` 恒等于 1，那句「初值不是 1 是 1 % p」也用不上；
//   ③ ★ **p < 2³¹** ⇒ `(p-1)² < 2⁶²` ⇒ **long long 刚好够，不用 __int128**。
//      余量正好是 √2：装得下的上限是 2³¹·⁵ ≈ 3.04×10⁹，而题面给到 2³¹ ≈ 2.15×10⁹。
//
// ⚠ 而这道题真正会挂人的一条和算法无关：**输出格式**是 `a^b mod p=s`，不是一个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;

    ll a0 = a, b0 = b;                 // 输出里要原样打出来，先存一份
    ll res = 1 % p;                    // p >= 2 ⇒ 这里就是 1；写 1 % p 只是习惯
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;  // (p-1)² < 2⁶²，long long 装得下
        a = a * a % p;
        b >>= 1;
    }

    printf("%lld^%lld mod %lld=%lld\n", a0, b0, p, res);
    return 0;
}

// P1226 ⚠ 错法零：算得完全对，只输出了一个数
//
// 这是把第 42 章的模板原样搬过来最容易出的事 ——
// 那一章的 fast.cpp 输出的就是一个数，因为那一章讲的是算法。
//
// 而这道题要的是：
//     a^b mod p=s
// 一个字符都不能差（`mod` 两边各一个空格、等号两边**没有**空格）。
//
// ⇒ 交上去 0 分，而你在本地怎么看都觉得答案是对的。
// ★ 这类错对拍抓得到 —— 但前提是**参照物也照着格式输出**，而且比对**不许 strip**。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;
    ll res = 1 % p;
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    printf("%lld\n", res);             // ⚠ 就是这里
    return 0;
}

// P1226 第 ① 版：老老实实连乘 b 次
//
// 它是对的，只是 b 能到 2³¹-1 ≈ 2.15×10⁹ ——
// 一次乘法 + 一次取模按 1.5 纳秒算，光这一步就是 **3 秒以上**，时限 1 秒。
//
// ⚠ 而它在样例上完全正确（b = 10），本地随手试也看不出任何问题。
// 这就是这道题的第一道坎：**样例的 b 和顶格的 b 差了两亿倍。**
//
// 为了让它在页面上点得动，这一版带一个上限：b 超过 3×10⁸ 就直接罢工报一行字。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;
    ll a0 = a, b0 = b;
    if (b > 300000000LL) {
        printf("b = %lld，连乘要跑 %lld 次 —— 这一版就不跑了，见页面上的外推。\n", b, b);
        return 0;
    }
    ll res = 1 % p;
    a %= p;
    for (ll i = 0; i < b; i++) res = res * a % p;
    printf("%lld^%lld mod %lld=%lld\n", a0, b0, p, res);
    return 0;
}

// ★★★ 把第 42 章列的**六个错法**，逐个代进 P1226 的数据范围
//
// 用法：./p1226Six [轮数]        人话版（默认 300 轮）
//       ./p1226Six [轮数] csv    给 check:viz 用
//
// 第 42 章第 ⑧ 步给了一张「靠什么现形」的清单。这一页想问的是另一个问题：
//
//   > **那六个错法，在 P1226 这道题的数据范围里，有几个是根本发生不了的？**
//
// 题面：`0 <= a, b < 2³¹`，`a + b > 0`，`2 <= p < 2³¹`。三处硬约束：
//   ① `a >= 0`     ⇒ 「负数要归一化」那条**永远用不上**；
//   ② `p >= 2`     ⇒ `1 % p` 恒等于 1，「初值不是 1」那条**永远用不上**；
//   ③ `p < 2³¹`    ⇒ `(p-1)² < 2⁶²`，**long long 刚好够** ——
//      装得下的上限是 `2³¹·⁵ ≈ 3.04×10⁹`，题面给到 `2³¹ ≈ 2.15×10⁹`，
//      ★ **余量正好是 √2**（一个是 2 的 31 次方，一个是 31.5 次方）。
//
// 所以这份程序跑**三档**，同一批错法 —— 三档是为了把「0 次」的两种原因分开：
//   档 A  **照题面顺手随机**；
//   档 A' **仍然照题面**，但专门把两个边界**配在一起**（b = 0 且 a ≡ 0 mod p）；
//   档 B  **把题面那三处各放宽一点**（允许 a < 0 / p = 1 / p 到 2³²）。
// ⇒ 在 A 是 0、在 A' 活了 ⇒ 题面**允许**，只是顺手生成器造不到；
//   在 A 和 A' 都是 0、只有 B 活 ⇒ 题面**结构上挡死了**它。
//
// ⚠ 演示溢出的那一版用的是 unsigned 乘法（回绕是标准规定的），
//   真写 `long long` 相乘溢出是 UB，-O2 下不可复现 —— 那样这一页的数就钉不住了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

/* 参照物：处处正确（__int128 乘法、负数归一化、1 % p、0⁰ = 1） */
static ll okFull(ll a, ll b, ll p) {
    ll res = 1 % p;
    a %= p; if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (ll)((lll)res * a % p);
        a = (ll)((lll)a * a % p);
        b >>= 1;
    }
    return res;
}
static ll wrongLoop(ll a, ll b, ll p) {          // while (b > 1)：最后一位没乘进去
    ll res = 1 % p; a %= p; if (a < 0) a += p;
    while (b > 1) {
        if (b & 1) res = (ll)((lll)res * a % p);
        a = (ll)((lll)a * a % p);
        b >>= 1;
    }
    return res;
}
static ll wrongOrder(ll a, ll b, ll p) {         // 先平方、再判这一位 —— 整整错一位
    ll res = 1 % p; a %= p; if (a < 0) a += p;
    while (b) {
        a = (ll)((lll)a * a % p);
        if (b & 1) res = (ll)((lll)res * a % p);
        b >>= 1;
    }
    return res;
}
static ll wrongNeg(ll a, ll b, ll p) {           // 不把负数归一化
    ll res = 1 % p; a %= p;                      // ⚠ 少了 if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (ll)((lll)res * a % p);
        a = (ll)((lll)a * a % p);
        b >>= 1;
    }
    return res;
}
/** 64 位乘法：`x * y` 超过 2⁶³ 就회绕成负数 —— 用 unsigned 算再当成有符号看，结果可复现。 */
static ll mul64(ll x, ll y, ll p) {
    ll t = (ll)((unsigned long long)x * (unsigned long long)y);
    return t % p;                                 // t 变负数时这里就跟着负了
}
static ll wrongOverflow(ll a, ll b, ll p) {      // 乘法只用 64 位（第 42 章那一章要 __int128）
    ll res = 1 % p; a %= p; if (a < 0) a += p;
    while (b) {
        if (b & 1) res = mul64(res, a, p);        // ★ p > 3.04×10⁹ 时这里会翻车
        a = mul64(a, a, p);
        b >>= 1;
    }
    return res;
}
static ll wrongInt(ll a, ll b, ll p) {           // ★ 这道题真正的溢出线：用 32 位
    unsigned res = (unsigned)(1 % p), aa = (unsigned)(a % p), pp = (unsigned)p;
    while (b) {
        if (b & 1) res = res * aa % pp;
        aa = aa * aa % pp;
        b >>= 1;
    }
    return (ll)res;
}
static ll wrongOne(ll a, ll b, ll p) {           // 初值写成 1（不是 1 % p）
    ll res = 1; a %= p; if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (ll)((lll)res * a % p);
        a = (ll)((lll)a * a % p);
        b >>= 1;
    }
    return res;
}
static ll wrongZero(ll a, ll b, ll p) {          // 「底数 ≡ 0 就返回 0」—— 把 0⁰ 也吞了
    ll aa = a % p; if (aa < 0) aa += p;
    if (aa == 0) return 0;
    return okFull(a, b, p);
}

static const char* NAMES[7] = {
    "wrongLoop", "wrongOrder", "wrongNeg", "wrongOverflow", "wrongOne", "wrongZero", "wrongInt"
};
typedef ll (*Fn)(ll, ll, ll);
static Fn FNS[7] = { wrongLoop, wrongOrder, wrongNeg, wrongOverflow, wrongOne, wrongZero, wrongInt };

int main(int argc, char** argv) {
    int rounds = (argc > 1) ? atoi(argv[1]) : 300;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    /* 装得下的 p 的上限：最大的 p 使 (p-1)² < 2⁶³ */
    ll ovLimit = 0;
    {
        ll lo = 2, hi = 5000000000LL;
        while (lo < hi) {
            ll mid = lo + (hi - lo + 1) / 2;
            if ((lll)(mid - 1) * (mid - 1) < (lll)9223372036854775807LL) lo = mid; else hi = mid - 1;
        }
        ovLimit = lo;
    }

    int caught[3][7] = {{0}};
    int b0Rounds = 0, azeroRounds = 0;
    for (int lv = 0; lv < 3; lv++) {
        mt19937_64 rng(20260827ull + (unsigned)lv);
        for (int r = 0; r < rounds; r++) {
            ll a, b, p;
            if (lv == 0) {                                   // 档 A：照题面顺手随机
                p = 2 + (ll)(rng() % 2147483646ull);          // [2, 2³¹)
                b = (ll)(rng() % 2147483648ull);              // [0, 2³¹)
                a = (ll)(rng() % 2147483648ull);
                if (r % 7 == 0) b = 0;                        // 顺手也多造些 b = 0
                if (a + b == 0) a = 1;
                if (b == 0) { b0Rounds++; if (a % p == 0) azeroRounds++; }
            } else if (lv == 1) {                             // 档 A'：仍在题面内，两个边界配在一起
                p = 2 + (ll)(rng() % 1000000ull);             // p 小一点，好让 a = k·p 也塞得进 2³¹
                a = p * (1 + (ll)(rng() % 3));                // ★ a ≡ 0 (mod p)，且 a > 0
                b = 0;                                        // ★ 同时 b = 0
            } else {                                          // 档 B：三处各放宽一点
                p = 1 + (ll)(rng() % 4294967295ull);           // [1, 2³²)
                b = (ll)(rng() % 2147483648ull);
                a = (ll)(rng() % 4294967296ull) - 2147483648LL;// 允许负
                if (r % 5 == 0) p = 1;
                if (r % 7 == 0) b = 0;
                if (a + b == 0) a = 1;
            }
            ll want = okFull(a, b, p);
            for (int i = 0; i < 7; i++) if (FNS[i](a, b, p) != want) caught[lv][i]++;
        }
    }

    if (csv) {
        printf("rounds,%d\novLimit,%lld\nb0Rounds,%d\nazeroRounds,%d\n", rounds, ovLimit, b0Rounds, azeroRounds);
        for (int i = 0; i < 7; i++) printf("A_%s,%d\n", NAMES[i], caught[0][i]);
        for (int i = 0; i < 7; i++) printf("C_%s,%d\n", NAMES[i], caught[1][i]);
        for (int i = 0; i < 7; i++) printf("B_%s,%d\n", NAMES[i], caught[2][i]);
        return 0;
    }

    printf("同一批错法（第 42 章第 ⑧ 步那张清单），三档数据各 %d 轮：\n\n", rounds);
    printf("  %-16s %12s %12s %12s   %s\n", "错法", "A 顺手随机", "A' 配边界", "B 放宽题面", "结论");
    printf("  %-16s %12s %12s %12s\n", "----------------", "------------", "------------", "------------");
    for (int i = 0; i < 7; i++) {
        const char* verdict = "";
        if (caught[0][i] == 0 && caught[1][i] == 0 && caught[2][i] > 0) verdict = "★ 题面结构上挡死了它";
        else if (caught[0][i] == 0 && caught[1][i] > 0)                 verdict = "★ 题面允许，只是顺手造不到";
        else if (caught[0][i] > 0)                                      verdict = "白送";
        printf("  %-16s %9d/%d %9d/%d %9d/%d   %s\n", NAMES[i],
               caught[0][i], rounds, caught[1][i], rounds, caught[2][i], rounds, verdict);
    }
    printf("\n  档 A 里 b = 0 的有 %d 轮，其中 a ≡ 0 (mod p) 的有 %d 轮 —— wrongZero 靠的就是后面这个数。\n",
           b0Rounds, azeroRounds);
    printf("\n  ★ 那条溢出线：64 位乘法装得下的最大 p 是 %lld（≈ %.2f×10⁹），\n", ovLimit, ovLimit / 1e9);
    printf("    而题面给到 2³¹ - 1 = 2147483647（≈ 2.15×10⁹）—— 余量 %.3f 倍，正好是 √2。\n",
           (double)ovLimit / 2147483647.0);
    printf("    ⇒ **long long 刚好够，不用 __int128** —— 这是算出来的，不是猜的。\n");
    return 0;
}

// P1226 ⚠ 错法：把 res / a / p 都放进 32 位
//
// 这是这道题**唯一一个真的会因为溢出而挂**的写法：
//   p 到 2³¹-1 ⇒ `res * a` 最大 (p-1)² ≈ 4.6×10¹⁸，32 位装 4.29×10⁹ 都够呛。
//
// ★ 对照第 42 章那条「乘法要用 __int128」：那一章的 p 能到 10¹⁸，所以非 __int128 不可；
//   这道题 p < 2³¹ ⇒ (p-1)² < 2⁶² ⇒ **long long 刚好够**（余量 √2，见 p1226Six.cpp）。
//   ⇒ **同一句提醒，换一道题就从「命门」变成「用不上」。判据只有一个：把范围代进去算。**
//
// ⚠ 这里写 unsigned 而不是 int：有符号溢出是 UB，-O2 下不可复现，页面上的数就钉不住了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;
    ll a0 = a, b0 = b;

    unsigned res = (unsigned)(1 % p), aa = (unsigned)(a % p), pp = (unsigned)p;
    while (b) {
        if (b & 1) res = res * aa % pp;    // ⚠ 32 位相乘，回绕
        aa = aa * aa % pp;
        b >>= 1;
    }
    printf("%lld^%lld mod %lld=%u\n", a0, b0, p, res);
    return 0;
}

// 数据生成器（P1226 对拍用）：`./p1226Gen <seed> [level]`
//
//   level 0（默认）★ **照题面顺手随机**：0 <= a,b < 2³¹，2 <= p < 2³¹
//   level 1        ★★ **在题面内把两个边界配在一起**：b = 0 **且** a 是 p 的倍数
//                  —— 专门给 `wrongZero` 用的。题面允许，顺手随机造不出来。
//   level 2        顶格：p 和 b 都贴着 2³¹-1（量的是速度，不是正确性）
//   level 3        b 很小（<= 30）—— 这一档连乘版跑得动，用来验「连乘 ≡ 快速幂」
//
// ⚠ 题面保证 a + b > 0，生成器必须照办（a = b = 0 那一组不合法，答案也没定义）。

#include <bits/stdc++.h>
using namespace std;
static mt19937_64 rng;
static long long ri(long long lo, long long hi) {
    return lo + (long long)(rng() % (unsigned long long)(hi - lo + 1));
}

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned long long)atoll(argv[1]) : 1ull);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    long long a, b, p;
    if (level == 1) {
        p = ri(2, 1000000);
        a = p * ri(1, 3);                 // ★ a ≡ 0 (mod p)，而且 a > 0
        b = 0;                            // ★ 同时 b = 0
    } else if (level == 2) {
        p = ri(2147000000LL, 2147483647LL);
        b = ri(2147000000LL, 2147483647LL);
        a = ri(2147000000LL, 2147483647LL);
    } else if (level == 3) {
        p = ri(2, 2147483647LL);
        b = ri(0, 30);
        a = ri(0, 2147483647LL);
        if (a + b == 0) a = 1;
    } else {
        p = ri(2, 2147483647LL);
        b = ri(0, 2147483647LL);
        a = ri(0, 2147483647LL);
        if (rng() % 7 == 0) b = 0;
        if (a + b == 0) a = 1;
    }
    printf("%lld %lld %lld\n", a, b, p);
    return 0;
}

// P1226 ⚠ 错法：顺手加了一句「底数是 0 就直接返回 0」
//
// 这是第 42 章清单里的 `wrongZero`，那一章说它要「**a ≡ 0 且 b = 0** 同时成立」才现形。
//
// ★ 这道题的题面把 `a + b > 0` 写死了 —— 于是 a = 0 且 b = 0 确实不可能。
//   但**「a ≡ 0 (mod p)」不等于「a = 0」**：a = p、2p、3p… 都行，而且它们都 > 0。
//   ⇒ 这个错法在这道题上**是能发生的**，只是顺手写的生成器造不出来
//     （要 b = 0 和 a 是 p 的倍数**同时**成立）。
//
// ⚠ 它和 wrongNeg / wrongOne / wrongOverflow 那三个不是一回事 ——
//   那三个是**题面结构上挡死的**，放宽题面才能活。
//   分辨方法见 p1226Six.cpp 那张三档表。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a, b, p;
    if (scanf("%lld %lld %lld", &a, &b, &p) != 3) return 0;
    ll a0 = a, b0 = b;

    ll res;
    if (a % p == 0) {
        res = 0;                          // ⚠ 就是这一句：0⁰ 也被它吞了
    } else {
        res = 1 % p;
        a %= p;
        while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
    }
    printf("%lld^%lld mod %lld=%lld\n", a0, b0, p, res);
    return 0;
}