快速幂与取模

// 标准答案 —— 老老实实乘 b 次
//
// 为什么它存在：
//   ① 它是对拍里的标准答案。想法和快速幂**完全不同**：一个是「按定义连乘」，
//      一个是「把指数拆成二进制」。（第 9、15 章那条规矩。）
//   ② ★ 它同时是这一章的反面教材：`b` 到 10¹⁸ 时它要乘十亿亿次 —— 跑到天荒地老。
//
// ⚠⚠ **于是这一章的对拍有一个前面十几章都没碰到过的限制：
//    标准答案只能在「b 很小」的数据上跑。**
//    ⇒ 生成器必须把 b 压在 10⁵ 以内，可题面允许 b 到 10¹⁸ ——
//      **那一半的取值范围，对拍根本够不着。**
//    ★ 补救办法见 verify.cpp：不比答案，**比性质**（a^(b₁+b₂) ≡ a^b₁ · a^b₂）。
//      这是第 31 章「答案不唯一时写验证器」那一招的**另一种用法**：
//      **这次答案是唯一的，够不着的是「规模」。**
//
// ⚠ 取模的三件事它一件都不能少（和正解一模一样，否则对拍对的是两个错的东西）：
//   负数先归一化、乘法用 __int128、初值写 `1 % p`。

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

using ll = long long;
using i128 = __int128;

/** a^b mod p，按定义连乘 b 次 */
ll powerBrute(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ p = 1 时是 0
    a %= p;
    if (a < 0) a += p;
    for (ll i = 0; i < b; i++) res = (i128)res * a % p;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = powerBrute(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 快速幂（反复平方法）
//
// ============ ★ 关键一步：a^b = (a^(b/2))² ============
//
//   b 是偶数：a^b = (a^(b/2))²
//   b 是奇数：a^b = a · (a^((b−1)/2))²
//
//   ⇒ **每一步把指数砍一半**，所以只要 ⌊log₂b⌋ + 1 步。这就是第 12 章那个分治的形状：
//     把一个大问题换成**同形状的、规模减半的**小问题。
//
//   写成迭代版更好记 —— **把 b 看成二进制**：
//     b = 13 = 1101₂  ⇒  a¹³ = a⁸ · a⁴ · a¹
//   于是「从低位往高位扫 b，位是 1 就把当前的 a^(2^k) 乘进答案」：
//
//     res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; }
//
//   ★ 乘法次数 = **popcount(b) + ⌊log₂b⌋**（乘进答案的次数 + 平方的次数）——
//     和第 38 章树状数组那个「步数恰好等于 popcount」是同一种数法。
//
// ============ ⚠⚠ 这一章一半的内容在「取模」上，而不是在「快速幂」上 ============
//
//   **① 乘法溢出。** `p` 可以到 10¹⁸，那么 `res * a` 就是 10³⁶ —— **long long 装不下**。
//      这里用 `__int128` 兜住（GCC 扩展，OI 里可以用）。
//      ⚠ 没有 __int128 的时候怎么办？见 mul.cpp（龟速乘：把乘法也拆成二进制）。
//
//   **② 负数取模。** C++ 的 `%` 对负数给的是**负余数**（`-7 % 3 == -1`），
//      而题面要的答案在 `[0, p)` 里。所以读进来第一件事就是
//      `a = ((a % p) + p) % p` —— **两次取模，一次都不能少**。
//
//   **③ b = 0 和 p = 1 这两个边界。**
//      `a^0 = 1`，可如果 `p = 1`，答案是 **0**（任何数模 1 都是 0）。
//      所以初值不能直接写 `res = 1`，得写 `res = 1 % p`。
//      ★ 这一句是这一章最容易漏、也最容易被小数据蒙混过去的一行。
//
// 复杂度：每组询问 O(log b)。

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

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：循环条件写成 `while (b > 1)`
//
//   于是最后一位（b == 1 那一次）**没有被乘进答案**，结果整整少乘一个 a。
//
// 靠什么现形：几乎什么数据都行 —— **只要 b ≥ 1**。★ 它是这一章的基线。
// ⚠ 但注意 b = 0 时它是对的（循环本来就不进），所以「只造 b = 0」的数据抓不到它。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b > 1) {                                // ✗ 最后一位没乘进去
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：**先平方、再判这一位**（两句话调了个个儿）
//
//   ```
//   a = a * a % p;                 ← ✗ 先把 a 平方了
//   if (b & 1) res = res * a % p;  ← ✗ 于是乘进答案的是 a^(2^(k+1))，整整错一位
//   ```
//
// 靠什么现形：**b 的二进制里至少有一个 1**，也就是 b ≥ 1 —— 同样几乎白送。
// ★ 它和 wrongLoop 是一对：**同样是「错一位」，一个错在最后一位，一个错在每一位。**
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        a = (i128)a * a % p;                       // ✗ 先平方了
        if (b & 1) res = (i128)res * a % p;        // ✗ 于是乘进去的是错一位的那个
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：**没把负数归一化**（少了那句 `if (a < 0) a += p;`）
//
//   C++ 的 `%` 对负数给的是**负余数**：`-7 % 3 == -1`（不是 2）。
//   于是 a 是负数时，答案会变成一个负数 —— 而题面要的是 `[0, p)` 里的数。
//
// 靠什么现形：★ 询问里必须有 **a < 0**，而且**指数是奇数**
//   （偶次幂会把负号平方掉，答案照样对）。
//   ⚠ 两个条件要同时满足 —— 这是「两件事都得发生」的又一次（第 36 章那条）。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;                                        // ✗ 少了 if (a < 0) a += p;
    while (b) {
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：乘法**没用 __int128**，直接 `res * a % p`
//
// 靠什么现形：★ 要 `res × a` 撞破 long long（≈9.2×10¹⁸）——
//   也就是 **p 得足够大**（p 到 3×10⁹ 以上时两个接近 p 的数一乘就爆了）。
//   ⚠ 而「顺手」写的生成器多半把 p 取在 10⁹ 附近（「模数嘛，10⁹+7」）——
//   **那正好是它安全的上限**：`(10⁹)² = 10¹⁸ < 9.2×10¹⁸`。
//   ★ 所以这个 bug 要的不是「p 大」，是 **p 大过某一条具体的线**（约 3.04×10⁹ = √(2⁶³)）。
// ⇒ 第 38、40 章那条：**先估一估多大的数据才溢出，再决定拧到哪一格。**
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        if (b & 1) res = res * a % p;              // ✗ 没兜住：p 一大这里就溢出
        a = a * a % p;                             // ✗ 同上
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：初值写成 `res = 1`，而不是 `res = 1 % p`
//
//   `a^0 = 1` 没错，可题面要的是 **`a^b mod p`** —— 而 `p = 1` 时任何数都 ≡ 0。
//   于是它在 `p = 1` 时输出 1，正解输出 0。
//
// 靠什么现形：★★ 询问里必须出现 **p = 1**。
//   ⚠ 而「顺手」写的生成器多半是 `p = rnd(2, 10⁹)` 或者干脆写死 `10⁹+7` ——
//   **p = 1 这个边界随机撞不到**（`1 ≤ p` 是题面写死的）。
//   ★ 第 41 章那条的同款：**有些 bug 要的是「某一个特定的数」，只能专门塞。**
// ⚠ 顺带：b = 0 时它同样错（res 一次都没被乘过，直接返回 1）——
//   所以这个 bug 有两条腿，可两条腿要的是同一个东西：**p = 1**。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1;                                    // ✗ 忘了模 p：p = 1 时答案该是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// ✗ 错误版本：把 `0⁰` 当成了 0
//
//   题面约定 **`0⁰ = 1`**（然后再模 p）。这份代码顺手加了一句「底数是 0 就直接返回 0」——
//   看着挺合理，可它把 `b = 0` 那一支也一起吞了。
//
// 靠什么现形：★★ 询问里必须同时出现 **a ≡ 0 (mod p) 且 b = 0**。
//   ⚠ 随机数据里 b = 0 的概率是 1/(b 的取值个数)，a ≡ 0 的概率是 1/p ——
//   **两个都靠运气的话，这辈子都撞不上。**
//   ⇒ 生成器必须**同时**专门塞 b = 0 和 a = 0。★ 第 41 章那条「专门塞某个数」的加强版：
//     这次要**两个特定的数一起出现**。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;
    a %= p;
    if (a < 0) a += p;
    if (a == 0) return 0;                          // ✗ 顺手加的一句：把 0⁰ = 1 也吞掉了                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 快速幂（反复平方法）
//
// ============ ★ 关键一步：a^b = (a^(b/2))² ============
//
//   b 是偶数：a^b = (a^(b/2))²
//   b 是奇数：a^b = a · (a^((b−1)/2))²
//
//   ⇒ **每一步把指数砍一半**，所以只要 ⌊log₂b⌋ + 1 步。这就是第 12 章那个分治的形状：
//     把一个大问题换成**同形状的、规模减半的**小问题。
//
//   写成迭代版更好记 —— **把 b 看成二进制**：
//     b = 13 = 1101₂  ⇒  a¹³ = a⁸ · a⁴ · a¹
//   于是「从低位往高位扫 b，位是 1 就把当前的 a^(2^k) 乘进答案」：
//
//     res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; }
//
//   ★ 乘法次数 = **popcount(b) + ⌊log₂b⌋**（乘进答案的次数 + 平方的次数）——
//     和第 38 章树状数组那个「步数恰好等于 popcount」是同一种数法。
//
// ============ ⚠⚠ 这一章一半的内容在「取模」上，而不是在「快速幂」上 ============
//
//   **① 乘法溢出。** `p` 可以到 10¹⁸，那么 `res * a` 就是 10³⁶ —— **long long 装不下**。
//      这里用 `__int128` 兜住（GCC 扩展，OI 里可以用）。
//      ⚠ 没有 __int128 的时候怎么办？见 mul.cpp（龟速乘：把乘法也拆成二进制）。
//
//   **② 负数取模。** C++ 的 `%` 对负数给的是**负余数**（`-7 % 3 == -1`），
//      而题面要的答案在 `[0, p)` 里。所以读进来第一件事就是
//      `a = ((a % p) + p) % p` —— **两次取模，一次都不能少**。
//
//   **③ b = 0 和 p = 1 这两个边界。**
//      `a^0 = 1`，可如果 `p = 1`，答案是 **0**（任何数模 1 都是 0）。
//      所以初值不能直接写 `res = 1`，得写 `res = 1 % p`。
//      ★ 这一句是这一章最容易漏、也最容易被小数据蒙混过去的一行。
//
// 复杂度：每组询问 O(log b)。

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

using ll = long long;
using i128 = __int128;

/** a^b mod p，答案落在 [0, p) */
ll power(ll a, ll b, ll p) {
    ll res = 1 % p;                                // ★ 不是 1！p = 1 时答案是 0
    a %= p;
    if (a < 0) a += p;                             // ⚠ 负数取模：C++ 的 % 会给负余数
    while (b) {
        if (b & 1) res = (i128)res * a % p;        // ⚠ 用 __int128 兜住 10³⁶
        a = (i128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    if (!(cin >> q)) return 0;

    string out;
    int zeros = 0;
    for (int i = 0; i < q; i++) {
        ll a, b, p;
        cin >> a >> b >> p;
        ll v = power(a, b, p);
        if (v == 0) zeros++;
        out += to_string(v);
        out += '\n';
    }
    out += to_string(zeros);                       // ★ 末行：有多少组的答案是 0
    out += '\n';

    cout << out;
    return 0;
}