AtCoder Beginner Contest 444 题解

for-each2026年8月18日大约 21 分钟

AtCoder Beginner Contest 444 题解

项目	内容
比赛时间	2026-02-07
比赛链接	https://atcoder.jp/contests/abc444
题目数量	A–G 共 7 题

比赛概览

本场 ABC 444 整体难度前轻后重。A、B 是纯粹的送分题；C 是一道需要"分情况讨论 + 配对贪心"的构造判断题；D 是经典的"按位列竖式加法"大整数处理题，巧妙地避免了高精度；E 是滑动窗口 + 有序集合维护的经典双指针题；F 是二分答案 + 贪心计数，其中可行性判断的三个条件相当隐蔽，是本场最值得掌握的题之一；G 是压轴数论题，需要把问题化归为"模 $C$ 下计数平方和表示"，并用 Gauss 整数（唯一分解整环）处理，综合性很强。C、F、G 三题区分度明显。

A - Repdigit

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_a

题目大意

给定一个三位正整数 $N$ （ $100 \le N \le 999$ ），判断 $N$ 的十进制表示下三个数位是否全部相同。相同输出 Yes，否则输出 No。

思路

最直接的做法是把它当成字符串读入，比较 $N[0]==N[1]==N[2]$ 。

还有一个更漂亮的数论做法：设 $N$ 的三个数位为 $a,b,c$ ，则

N = 100a + 10b + c

若 $a = b = c$ ，则 $N = 111a$ ，即 $111 \mid N$ 。反过来，若 $111 \mid N$ ，由于 $100 \le N \le 999$ ，只能有 $N = 111k$ （ $k = 1,2,\dots,9$ ），即 $N = kkk$ ，三个数位都是 $k$ 。所以条件等价于 $N \% 111 == 0$ 。

本题没有需要特别小心的边界情况（ $N$ 恒为三位数）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    cout << (N % 111 == 0 ? "Yes" : "No") << '\n';
    return 0;
}

官方题解同样给出了 Python 版本（字符串比较）：

N = input()
if N[0] == N[1] == N[2]:
    print("Yes")
else:
    print("No")

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Digit Sum

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_b

题目大意

一个正整数 $n$ 的数位和定义为它十进制表示下各位数字之和（例如 $2026$ 的数位和为 $2+0+2+6=10$ ）。给定 $N, K$ （ $1 \le N,K \le 10^5$ ），求不超过 $N$ 的正整数中数位和恰好等于 $K$ 的个数。

思路

$N \le 10^5$ ，完全可以对每个 $i = 1,2,\dots,N$ 暴力求数位和并计数。求数位和时不断取个位再除以 $10$ 即可，写成独立函数会让代码更清晰：

\text{digit\_sum}(x) = \sum_{\text{十进制位}} \text{该位的数字}

实现时也可以用 to_string 把数字转成字符串后逐字符累加，效果相同。

复杂度分析：每个数至多 $6$ 位，总计算量约为 $6 \times 10^5$ 次，绰绰有余。

参考代码

#include <bits/stdc++.h>
using namespace std;
int digitsum(int x) {
    int s = 0;
    while (x) { s += x % 10; x /= 10; }
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    int ans = 0;
    for (int i = 1; i <= N; i++)
        if (digitsum(i) == K) ans++;
    cout << ans << '\n';
    return 0;
}

官方题解同样给出了 Python 版本：

def digitsum(x):
    s = str(x)
    ans = 0
    for c in s:
        ans += int(c)
    return ans

n, k = map(int, input().split())
ans = 0
for i in range(1, n + 1):
    if digitsum(i) == k:
        ans += 1
print(ans)

复杂度分析

时间复杂度： $O(N \log N)$ （每个数做 $O(\log N)$ 次除法取位）
空间复杂度： $O(1)$

C - AtCoder Riko

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_c

题目大意

杯子里最初有若干根长度均为 $L$ 的条状零食。摇动后，每根要么保持长度 $L$ 不变，要么断成两根正整数长度、和为 $L$ 的零食。已知最终有 $N$ 根零食，第 $i$ 根长度为 $A_i$ 。求出所有可能的初始长度 $L$ ，升序输出。数据保证至少存在一个合法的 $L$ 。

思路

先做关键观察：一根断开的零食的两段长度都严格小于 $L$ （两段都是正整数且和为 $L$ ）。因此：

最终状态中长度恰好等于 $L$ 的零食，必定是"没断"的原始零食；
其余长度 $< L$ 的零食，必定是某根零食断开后产生的两段，它们两两配对，且每对之和恰为 $L$ 。

把 $A$ 排序，设 $A_1 \le A_2 \le \dots \le A_N$ 。分两种情况讨论：

情况 1：所有原始零食都断开了。

此时每根原始零食恰好变成两根，故 $N$ 必须是偶数。设与最短零食 $A_1$ 配对的长度为 $y$ ，则 $y \le A_N$ ，故 $L = A_1 + y \le A_1 + A_N$ 。同理，与最长零食 $A_N$ 配对的长度不小于 $A_1$ ，故 $L \ge A_1 + A_N$ 。于是必须有 $L = A_1 + A_N$ ，且配对是被强制的： $A_1$ 配 $A_N$ 、 $A_2$ 配 $A_{N-1}$ 、……。检查每对 $(A_i, A_{N+1-i})$ 是否都等于 $A_1 + A_N$ 即可。若成立，则 $L = A_1 + A_N$ 是一个合法答案。

情况 2：存在没有断开的原始零食。

没有断开的零食长度就是 $L$ ，而所有断片长度都 $< L$ ，所以 $L$ 恰为最大值 $A_N$ 。所有长度为 $A_N$ 的零食都"没断"，删掉它们；剩下的（全部 $< A_N$ ）必须能两两配对、每对之和为 $A_N$ 。

判断"能否配对为若干对、每对和为 $L$ "是经典贪心：排序后双指针，最小配最大。若 $A_{lo} + A_{hi} < L$ ，则最小的 $A_{lo}$ 只能与 $L - A_{lo} > A_{hi}$ 配对，但 $A_{hi}$ 已是最大值，找不到这样的伙伴，失败；若 $A_{lo} + A_{hi} > L$ ，则最大的 $A_{hi}$ 只能与 $L - A_{hi} < A_{lo}$ 配对，但 $A_{lo}$ 已是最小值，同样失败；相等则配对并收缩指针。另外剩余个数必须是偶数（双指针结束后不能剩下单独一个元素）。

两个情况产生的 $L$ 可能有重合（用集合去重），且情况 1 的 $L = A_1 + A_N$ 恒大于情况 2 的 $L = A_N$ ，故去重后升序输出即可。

正确性由上面的推导保证：任何合法 $L$ 要么属于情况 1（全断）要么属于情况 2（存在没断的），两种情况都被逐一检查。

易错点：

情况 2 中删除的是所有等于 $A_N$ 的元素，因为它们都只能是没断的原始零食；
情况 2 若删完后只剩空集（所有元素都等于 $A_N$ ），合法；
情况 1 要求 $N$ 为偶数。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    set<ll> ans;

    // 情况 1：所有原始零食都断成两根
    if (N % 2 == 0) {
        ll L = a[0] + a[N - 1];
        bool ok = true;
        for (int i = 0; i < N / 2; i++) {
            if (a[i] + a[N - 1 - i] != L) { ok = false; break; }
        }
        if (ok) ans.insert(L);
    }

    // 情况 2：存在没断的原始零食，故 L = a[N-1]
    ll L = a[N - 1];
    bool ok = true;
    int hi = N - 1;
    while (hi >= 0 && a[hi] == L) hi--;   // 去掉所有长度为 L 的"没断"零食
    int lo = 0;
    // 剩余碎片必须两两配对、每对之和为 L
    while (lo < hi) {
        if (a[lo] + a[hi] != L) { ok = false; break; }
        lo++; hi--;
    }
    if (lo == hi) ok = false;             // 剩单根，无法配对
    if (ok) ans.insert(L);

    bool first = true;
    for (ll v : ans) {
        if (!first) cout << ' ';
        cout << v;
        first = false;
    }
    cout << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （排序为瓶颈）
空间复杂度： $O(N)$

D - Many Repunit Sum

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_d

题目大意

对 $i = 1,\dots,N$ ，令 $B_i$ 为 $A_i$ 个 $1$ 连成的整数，即

B_i = \sum_{j=0}^{A_i-1} 10^j = \underbrace{111\cdots 1}_{A_i\ \text{个}}

求 $\sum_{i=1}^{N} B_i$ 。答案可能非常大（不能按普通整数输出）。

思路

直接构造每个 $B_i$ 再相加有两个问题：一是构造 $N$ 个大整数需要 $O(N^2)$ 时间；二是要手写高精度。用"按列竖式加法"可以同时避开两者。

设 $C_k$ 为 $10^k$ 在总和中出现的次数（即答案中 $10^k$ 位的系数）。由于 $B_i$ 只包含 $10^0, 10^1, \dots, 10^{A_i-1}$ 这些位， $10^k$ 出现在 $B_i$ 中当且仅当 $k < A_i$ ，故

C_k = \#\{i : A_i > k\}

先用频数数组统计每个值出现的次数，再从大到小做后缀和，就能在 $O(N + \max A)$ 内求出 $C_0, C_1, \dots, C_{\max A - 1}$ （而 $C_k = 0$ 对 $k \ge \max A$ ）。

然后做进位（这就是竖式加法的进位过程）：从低位 $i = 0$ 开始，

C_{i+1} \gets C_{i+1} + \left\lfloor \frac{C_i}{10} \right\rfloor, \qquad C_i \gets C_i \bmod 10

不断向高位推进，直到超出最高位且系数为 $0$ 。最终每个 $C_i$ 都是 $0\sim 9$ 的数字，且 $C_i$ 就是答案的第 $i$ 位（个位是 $i=0$ ）。输出时从最高非零位倒序打印即可。

关于数组长度的估计：答案

\sum_i B_i \le N \times B_{\max} < 2 \times 10^5 \times 10^{\max A} < 10^{\max A + 6}

所以答案至多有 $\max A + 6$ 位，开一个 $\max A + 30$ 的数组足够容纳所有进位。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> a(N);
    int maxA = 0;
    for (int i = 0; i < N; i++) { cin >> a[i]; maxA = max(maxA, a[i]); }

    vector<ll> freq(maxA + 1, 0);
    for (int x : a) freq[x]++;

    const int SZ = maxA + 30;
    vector<ll> C(SZ, 0);
    // C[k] = 满足 A_i > k 的下标个数（10^k 在总和中出现的次数）
    ll suf = 0;
    for (int k = maxA - 1; k >= 0; k--) {
        suf += freq[k + 1];
        C[k] = suf;
    }

    // 竖式进位
    for (int i = 0; i + 1 < SZ; i++) {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    int last = SZ - 1;
    while (last > 0 && C[last] == 0) last--;
    for (int i = last; i >= 0; i--) cout << C[i];
    cout << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N + \max A)$
空间复杂度： $O(\max A)$

E - Sparse Range

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_e

题目大意

给定长度为 $N$ 的整数序列 $A_1,\dots,A_N$ 与正整数 $D$ 。求满足以下条件的整数对 $(L,R)$ 的个数： $1 \le L \le R \le N$ ，且区间 $[L,R]$ 内任意两个元素的差的绝对值都不小于 $D$ ，即对任意 $L \le i < j \le R$ 有 $|A_i - A_j| \ge D$ 。

思路

关键观察 1：对固定的 $L$ ，合法的 $R$ 构成一个前缀。

若 $(L,R)$ 不合法，说明区间内存在 $i < j$ 使 $|A_i - A_j| < D$ ；那么对任何 $R' \ge R$ ，区间 $[L,R']$ 仍包含这对元素，也一定不合法。因此存在一个 $f(L)$ ，使得 $(L,L),\dots,(L,f(L))$ 全部合法，而 $(L,f(L)+1),\dots,(L,N)$ 全部不合法。

关键观察 2： $f(L)$ 关于 $L$ 单调不降。

$(L,f(L))$ 合法意味着 $(L+1,f(L))$ 也合法（少了一堆要检查的元素对）。于是可以用滑动窗口（双指针）扫一遍：右指针 $R$ 单调递增。

如何快速判断能否把 $A_R$ 加入当前窗口？

若当前窗口 $(L, R-1)$ 合法，则 $(L,R)$ 合法当且仅当 $A_R$ 与窗口内所有元素之差都 $\ge D$ 。这等价于"窗口内最小的大于等于 $A_R$ 的元素 $\ge A_R + D$ ，且窗口内最大的小于等于 $A_R$ 的元素 $\le A_R - D$ "。

用 std::set（有序集合）维护当前窗口内的值，即可 $O(\log N)$ 支持：插入、删除、lower_bound（找最小的大于等于某个值的元素）、以及前驱（it--）。为了防止 lower_bound 返回 end()、或前驱越界，可以在集合里预先放入两个"哨兵"（一个极小值、一个极大值），且保证它们永远不会触发 break 条件。

伪代码框架：

ans = 0; R = 1
for L = 1..N:
    while (L, R) 合法: R <- R+1
    // 此时 (L,L)..(L,R-1) 均合法
    ans += R - L

实现细节：由于一旦窗口内出现与 $A_R$ 相等的元素就会因 $|A_R - A_R| = 0 < D$ 而停止扩张，窗口内不会有重复值，所以用 set（而非 multiset）即可，删除时直接 erase 该值。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    ll ans = 0;
    set<ll> s({(ll)-1e18, (ll)2e18});   // 两个哨兵
    int r = 0;
    for (int l = 0; l < n; l++) {
        while (r < n) {
            auto it = s.lower_bound(a[r]);
            if (*it - a[r] < d) break;   // 上方最近元素太近
            it--;
            if (a[r] - *it < d) break;   // 下方最近元素太近
            s.insert(a[r]);
            r++;
        }
        ans += r - l;                    // (l,l)..(l,r-1) 均合法
        s.erase(a[l]);                   // 窗口左移
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$
空间复杂度： $O(N)$

F - Half and Median

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_f

题目大意

有 $N$ 根木棍，第 $i$ 根长度为 $A_i$ 。每次操作选一根长度 $\ge 2$ 的木棍 $l$ ，切成 $\lfloor l/2 \rfloor$ 与 $\lceil l/2 \rceil$ 两根。共操作 $M$ 次（保证可以完成），最终有 $N+M$ 根木棍（该数恒为奇数），求所有木棍长度的中位数最大能是多少。有 $T$ 组数据，所有数据的 $N$ 之和不超过 $10^5$ 。

思路

$N+M$ 为奇数，设 $K = \frac{N+M+1}{2}$ ，则中位数就是第 $K$ 小的长度。"中位数能 $\ge X$ "等价于"最终至少有 $K$ 根木棍长度 $\ge X$ "。可行性关于 $X$ 单调，因此二分答案 $X$ ，把问题化为判断"能否恰好操作 $M$ 次且最终有至少 $K$ 根长度 $\ge X$ 的木棍"。

下面推导可行性判断。称长度 $\ge X$ 的木棍为好棍。

贪心切分

对一根木棍，一刀下去：

长度 $\ge 2X$ ：两段都 $\ge X$ ，好棍数 $+1$ ；
长度恰为 $2X-1$ ：切成 $X$ 与 $X-1$ ，好棍数不变；
长度 $< 2X-1$ ：好棍数不增反减。

因此"最大好棍数"由贪心给出：反复切分长度 $\ge 2X-1$ 的碎片，直到不存在为止。这个贪心还额外把所有 $2X-1$ 的碎片变成了 $X$ （有利于后面吸收多余操作）。

可行性三条件

设贪心后好棍总数为 $C$ ， $S$ 为贪心后最短的 $K$ 根好棍的长度和， $g_0$ 为初始好棍数 $\#\{i : A_i \ge X\}$ 。可行当且仅当下面三条同时成立：

$C \ge K$ ：好棍总数够用（贪心已达到最大）。
操作数下限： $\max(0,\, K - g_0) \le M$ 。因为每操作一次，好棍数最多增加 $1$ （只有切 $\ge 2X$ 的木棍才 $+1$ ）， $M$ 次操作后好棍数 $\le g_0 + M$ ，所以必须 $K \le g_0 + M$ 。
操作数上限： $K + \sum A - S - N \ge M$ 。推导如下：贪心结束后所有碎片都 $< 2X-1$ 。为在保持至少 $K$ 根好棍的前提下用掉尽量多的操作，保留 $K$ 根最短好棍不动（总长 $S$ ），把其余所有碎片切到底（每根都变成长度 $1$ ）。最终木棍数为 $K + (\sum A - S)$ ，操作数为

(K + \sum A - S) - N

这就是"能保持 $\ge K$ 根好棍"的最大操作数；只要它 $\ge M$ ，就能从 $0$ 逐步做到恰好 $M$ 次（每次多切一刀）。

这三条同时充分必要：下限保证"做得到"那么多好棍，上限保证"操作数用不完"， $C \ge K$ 保证好棍总量足够。

单根木棍的贪心结果

判断过程中需要对每根木棍求出贪心切分的碎片。对长度 $l$ 、阈值 $T = 2X-1$ ：若把一根木棍完全对半切 $d$ 层，第 $d$ 层的碎片长度只有 $\lfloor l/2^d \rfloor$ 与 $\lceil l/2^d \rceil$ 两种（对半切偏差至多 $1$ ）。取最小的 $d$ 使 $\lfloor l/2^d \rfloor < T$ ，则第 $d$ 层之前所有碎片都 $\ge T$ 会被切掉，第 $d$ 层的碎片就与"全切"一致：

若 $\lceil l/2^d \rceil < T$ ：所有碎片在此层停止，碎片为 $\lfloor l/2^d \rfloor$ （ $2^d - r$ 个）与 $\lceil l/2^d \rceil$ （ $r$ 个），其中 $r = l \bmod 2^d$ ；
若 $\lceil l/2^d \rceil = T = 2X-1$ ：此时 $\lfloor l/2^d \rfloor = T-1 = 2X-2$ ，且这些 $T$ 碎片还要再切一刀，产生 $X$ 与 $X-1$ 。最终好碎片为 $2X-2$ （ $2^d - r$ 个）与 $X$ （ $r$ 个）， $X-1$ 是坏碎片。

于是每根木棍至多贡献 3 种长度的好碎片， $O(\log l)$ 时间可得。把所有好碎片按长度聚合、排序，即可求出 $C$ 与 $S$ 。整个判断 $O(N \log \max A + N \log N)$ 。

特殊地， $X = 1$ 时任何操作都保证所有木棍 $\ge 1$ ，直接判定可行。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N;
        ll M;
        cin >> N >> M;
        vector<ll> A(N);
        ll sumA = 0, maxA = 0;
        for (auto& x : A) { cin >> x; sumA += x; maxA = max(maxA, x); }
        sort(A.begin(), A.end());
        ll K = (N + M + 1) / 2;   // 中位数为第 K 小的长度

        auto feasible = [&](ll X) -> bool {
            if (X == 1) return true;
            ll T = 2 * X - 1;     // 贪心切分阈值
            ll initGood = N - (lower_bound(A.begin(), A.end(), X) - A.begin());
            if (K - initGood > M) return false;   // 操作数下限

            vector<pair<ll, ll>> good;            // (长度, 个数) 的好碎片
            ll C = 0;                             // 贪心后好棍总数
            auto add = [&](ll len, ll cnt) {
                if (cnt <= 0) return;
                if (len >= X) { good.push_back({len, cnt}); C += cnt; }
            };
            for (ll l : A) {
                if (l < T) { add(l, 1); continue; }
                ll pw = 1;
                while (l / pw >= T) pw <<= 1;     // pw = 2^d, floor(l/2^d) < T
                ll f = l / pw;
                ll c = (l + pw - 1) / pw;
                ll r = l % pw;
                if (c < T) {
                    add(f, pw - r);
                    add(c, r);
                } else {                          // c == T == 2X-1
                    add(f, pw - r);               // f = 2X-2, 是好碎片
                    add(X, r);                    // ceil(T/2) = X, 是好碎片
                }
            }
            if (C < K) return false;

            sort(good.begin(), good.end());
            ll S = 0, need = K;
            for (auto& [len, cnt] : good) {
                ll take = min(need, cnt);
                S += take * len;
                need -= take;
                if (need == 0) break;
            }
            ll maxOps = K + sumA - S - N;         // 保持 >= K 根好棍的最大操作数
            return maxOps >= M;
        };

        ll lo = 1, hi = maxA, ans = 1;
        while (lo <= hi) {
            ll mid = (lo + hi) / 2;
            if (feasible(mid)) { ans = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O\bigl(N(\log \max A)^2 + N\log N \log \max A\bigr)$ （二分 $O(\log \max A)$ 轮，每轮 $O(N \log \max A)$ 求碎片 + $O(N \log N)$ 排序）
空间复杂度： $O(N)$

G - Kyoen

题目链接：https://atcoder.jp/contests/abc444/tasks/abc444_g

题目大意

平面上有一个圆，圆心为 $\left(\frac{A}{C}, \frac{B}{C}\right)$ ，半径为 $\frac{\sqrt{N}}{C}$ 。 $N$ 以质因数分解形式给出： $N = \prod_{i=1}^{M} P_i^{E_i}$ 。求落在圆周上的格点（整点）个数，对 $998244353$ 取模。

思路

本题的核心是数论：圆上有理点计数，需要用到 Gauss 整数（形如 $a + b\sqrt{-1}$ 、 $a,b$ 为整数的复数）。

第一步：转化为平方和 + 同余问题

格点 $(x,y)$ 在圆上当且仅当

\left(x - \frac{A}{C}\right)^2 + \left(y - \frac{B}{C}\right)^2 = \frac{N}{C^2}

两边乘 $C^2$ ，并令 $X = Cx - A,\ Y = Cy - B$ ，得

X^2 + Y^2 = N, \qquad X \equiv -A \pmod C,\quad Y \equiv -B \pmod C

且每个满足条件的 $(X,Y)$ 唯一对应一个格点 $\left(\frac{X+A}{C}, \frac{Y+B}{C}\right)$ 。问题变成：统计满足 $X^2+Y^2=N$ 且 $X \equiv -A,\ Y \equiv -B \pmod C$ 的整数对个数。

第二步：Gauss 整数与质因数分解

把 $(X,Y)$ 写成 Gauss 整数 $g = X + Yi$ ，其范数 $N(g) = X^2 + Y^2$ 。于是问题就是数满足 $g \cdot \overline{g} = N$ 且模 $C$ 落在指定剩余类的 $g$ 。

Gauss 整数环是唯一分解整环（UFD）。有理素数在其中分解为：

$2 = (1+i)(1-i)$ ，且 $1-i = -i(1+i)$ ，故 $2$ 与 $(1+i)^2$ 相伴；
$p \equiv 1 \pmod 4$ ：存在整数 $x,y$ 使 $p = x^2 + y^2 = (x+yi)(x-yi)$ ，两个因子都是 Gauss 素数；
$p \equiv 3 \pmod 4$ ： $p$ 本身是 Gauss 素数。

由唯一分解，设

N = 2^{e_2} \prod_{p \equiv 1} p^{e_p} \prod_{q \equiv 3} q^{e_q}

则满足 $g\overline{g} = N$ 的 $g$ 必可写成（相差单位 $i^k$ 的意义下）

g = i^k\, (1+i)^{e_2} \prod_{p\equiv 1} \pi_p^{\,e_p - k_p}\, \overline{\pi_p}^{\,k_p} \prod_{q\equiv 3} q^{e_q/2}, \qquad k \in \{0,1,2,3\},\ k_p \in [0, e_p]

其中 $\pi_p$ 是满足 $\pi_p\overline{\pi_p} = p$ 的 Gauss 素数。若某个 $e_q$ 是奇数，则答案为 $0$ 。利用 $\pi_p \overline{\pi_p} = p$ ，上式可改写为

g = i^k\, (1+i)^{e_2} \prod_{p\equiv1} p^{k_p}\, \pi_p^{\,e_p - 2k_p} \prod_{q\equiv3} q^{e_q/2}

第三步：按剩余类计数

固定因子 $\text{base} = (1+i)^{e_2} \prod_{q\equiv3} q^{e_q/2} \pmod C$ 、4 个单位 $i^k$ ，以及每个 $p \equiv 1$ 的"拆分选择" $k_p \in [0, e_p]$ 。用 DP/卷积 合并各素数在模 $C$ 意义下的剩余分布（两个剩余 $(x_1,y_1)\cdot(x_2,y_2) = (x_1x_2 - y_1y_2,\ x_1y_2 + y_1x_2)$ ，逐分量模 $C$ ）。

对单个 $p \equiv 1$ 、指数 $e$ ，需要求出多重集

\Bigl\{ p^{k}\, \pi^{\,e-2k} \bmod C : k \in [0,\, e] \Bigr\}

的分布。注意到 $k$ 与 $e-k$ 对应的两个值互为共轭，因此只需计算 $k \in [0, e/2]$ 的"半份"再翻倍（当 $e$ 为偶数时，中间的 $k = e/2$ 对应实数 $p^{e/2}$ ，只算一次）。

指数 $e$ 可达 $10^{18}$ ，不能枚举。关键事实：序列 $(p^k \bmod C,\ \pi^k \bmod C)$ 的状态空间大小不超过 $C \cdot C^2 = C^3$ （ $p^k$ 有 $C$ 种、 $\pi^k$ 是模 $C$ 的二元组有 $C^2$ 种），由鸽巢原理它必然进入周期，且"前导段 + 周期"总长 $\le C^3$ 。因此对 $k = 0,1,2,\dots$ 用快幂逐项计算 $\pi^{\,e-2k} \bmod C$ 并检测重复状态，即可在 $O(C^3)$ 内求出分布（周期部分按整除计数累加）。

第四步：合并与答案

初始分布为 4 个单位乘 $\text{base}$ 的剩余类（各计 $1$ ），依次与每个 $p \equiv 1$ 的分布做乘积卷积（ $O(C^4)$ ）。最终答案就是分布中目标剩余类 $(-A \bmod C,\ -B \bmod C)$ 的计数，对 $998244353$ 取模。

复杂度： $O\bigl(P^{1.5} + M C^3 + M C^4\bigr)$ ，其中 $P = \max P_i \le 100$ ， $C \le 50$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

struct G { ll x, y; };  // x + y*i，分量均取模 C

static inline ll norm(ll v, ll C) { return ((v % C) + C) % C; }

G gmul(G a, G b, ll C) {
    return { norm(a.x * b.x - a.y * b.y, C), norm(a.x * b.y + a.y * b.x, C) };
}

G gpow(G b, ll e, ll C) {          // Gauss 整数快速幂（模 C）
    G r{1 % C, 0};
    while (e) {
        if (e & 1) r = gmul(r, b, C);
        b = gmul(b, b, C);
        e >>= 1;
    }
    return r;
}

ll ipow(ll a, ll e, ll C) {        // 普通整数快速幂（模 C）
    a %= C;
    ll r = 1 % C;
    while (e) {
        if (e & 1) r = r * a % C;
        a = a * a % C;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll A, B, C;
    int M;
    cin >> A >> B >> C >> M;
    vector<ll> P(M), E(M);
    for (int i = 0; i < M; i++) cin >> P[i] >> E[i];

    ll e2 = 0;
    vector<pair<ll, ll>> p1, q3;
    for (int i = 0; i < M; i++) {
        if (P[i] == 2) e2 = E[i];
        else if (P[i] % 4 == 1) p1.push_back({P[i], E[i]});
        else q3.push_back({P[i], E[i]});
    }
    for (auto& [q, e] : q3)
        if (e % 2) { cout << 0 << '\n'; return 0; }

    int C2 = (int)(C * C);
    vector<ll> dist(C2, 0);

    // 固定因子 base = (1+i)^{e2} * prod q^{e_q/2} (mod C)
    G base = gpow({1, 1}, e2, C);
    for (auto& [q, e] : q3) base = gmul(base, {ipow(q, e / 2, C), 0}, C);

    // 4 个单位乘 base，作为初始分布
    G unit[4] = { {norm(1, C), 0}, {0, norm(1, C)}, {norm(-1, C), 0}, {0, norm(-1, C)} };
    for (int k = 0; k < 4; k++) {
        G g = gmul(unit[k], base, C);
        dist[(int)(g.x * C + g.y)] = (dist[(int)(g.x * C + g.y)] + 1) % MOD;
    }

    for (auto& [p, e] : p1) {
        // 求 pi = x + yi 使 x^2 + y^2 = p
        ll x0 = 0, y0 = 0;
        for (ll x = 1; x * x < p; x++) {
            ll y2 = p - x * x;
            ll y = (ll)sqrt((double)y2);
            while (y * y < y2) y++;
            while (y * y > y2) y--;
            if (y * y == y2) { x0 = x; y0 = y; break; }
        }
        G pi{x0 % C, y0 % C};

        ll K = e / 2;
        // 计算多重集 { p^k * pi^{e-2k} mod C : k in [0, K] } 的分布（"半份"）
        // 状态 = (p^k mod C, pi^{e-2k} mod C)，状态空间大小 <= C^3，必入循环
        int C3 = C2 * (int)C;
        vector<int> first(C3, -1);
        vector<pair<int, int>> states;   // (p^k mod C, pi^{e-2k} 剩余类下标)
        ll pk = 1 % C;
        int k = 0, mu = -1, P = -1;
        for (; k <= K; k++) {
            G gk = gpow(pi, e - 2 * k, C);
            int gidx = (int)(gk.x * C + gk.y);
            int state = (int)(pk * C2 + gidx);
            if (first[state] != -1) { mu = first[state]; P = k - mu; break; }
            first[state] = k;
            states.push_back({(int)pk, gidx});
            pk = pk * (p % C) % C;
        }

        vector<ll> half(C2, 0);
        auto addHalf = [&](int pkv, int gidx, ll w) {
            G f = gmul({(ll)pkv, 0}, {gidx / C, gidx % C}, C);
            int idx = (int)(f.x * C + f.y);
            half[idx] = (half[idx] + w) % MOD;
        };
        if (mu == -1) {                        // K 范围内未出现循环
            for (int i = 0; i <= K; i++) addHalf(states[i].first, states[i].second, 1);
        } else if (K < mu + P) {               // 只用了前导段
            for (int i = 0; i <= K; i++) addHalf(states[i].first, states[i].second, 1);
        } else {                               // 周期部分按整除计数
            for (int i = 0; i < mu; i++) addHalf(states[i].first, states[i].second, 1);
            ll total = K - mu + 1;
            ll q = total / P, rr = total % P;
            for (int j = 0; j < P; j++) {
                ll w = q + (j < rr ? 1 : 0);
                int i = mu + j;
                addHalf(states[i].first, states[i].second, w % MOD);
            }
        }

        // 完整分布 = 半份 + 共轭半份；e 为偶数时中间元素（实数）只算一次
        vector<ll> dist_p(C2);
        for (int i = 0; i < C2; i++) {
            ll x = i / C, y = i % C;
            int cj = (int)(x * C + (C - y) % C);   // 共轭剩余类
            dist_p[i] = (half[i] + half[cj]) % MOD;
        }
        if (e % 2 == 0) {
            ll mid = ipow(p % C, K, C);
            int idx = (int)(mid * C + 0);
            dist_p[idx] = (dist_p[idx] - 1 + MOD) % MOD;
        }

        // 乘积卷积：newdist[r1*r2] += dist[r1] * dist_p[r2]
        vector<ll> nd(C2, 0);
        for (int r1 = 0; r1 < C2; r1++) {
            if (!dist[r1]) continue;
            ll x1 = r1 / C, y1 = r1 % C;
            for (int r2 = 0; r2 < C2; r2++) {
                if (!dist_p[r2]) continue;
                ll x2 = r2 / C, y2 = r2 % C;
                ll nx = norm(x1 * x2 - y1 * y2, C);
                ll ny = norm(x1 * y2 + y1 * x2, C);
                int idx = (int)(nx * C + ny);
                nd[idx] = (nd[idx] + dist[r1] * dist_p[r2]) % MOD;
            }
        }
        dist = move(nd);
    }

    ll tX = norm(-A, C), tY = norm(-B, C);
    cout << dist[(int)(tX * C + tY)] % MOD << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O\bigl(P^{1.5} + M C^3 + M C^4\bigr)$ ，其中 $P = \max P_i \le 100$ 、 $C \le 50$ （求 $\pi_p$ 至多 $O(\sqrt P)$ ；单个素数的分布用循环检测在 $O(C^3)$ 内完成；合并分布 $O(C^4)$ ）
空间复杂度： $O(C^3)$

（完）