题解

思路推导

直接枚举三个下标需要 $O(N^3)$；枚举 $i,j$ 后，$k$ 至多有一个候选值，可以降到 $O(N^2)$。满分范围中 $N$ 达到 $10^6$，还需要把固定 $i$ 后的二元一次不定方程在常数时间内计数。

固定 $i$，令 $Y=X-Ai$。问题变为统计

它的所有整数解构成一个等差参数族，因此只要求出参数的合法整数区间即可。

做法

令 $g=\gcd(B,C)$。若 $g\nmid Y$，当前 $i$ 没有贡献。否则同时除以 $g$：

此时 $\gcd(b,c)=1$。用扩展欧几里得求 $b$ 在模 $c$ 意义下的逆元，得到满足 $bj_0\equiv y\pmod c$ 的一个 $j_0$，再令

全部整数解可以写成

其中 $t$ 为整数。把 $1\le j\le N$ 与 $1\le k\le N$ 分别转成 $t$ 的上下界，两个闭区间求交后即可得到当前 $i$ 的解数。枚举所有 $i$ 并累加。

正确性证明

当 $g\nmid Y$ 时，线性组合 $Bj+Ck$ 必为 $g$ 的倍数，故无解。当 $g\mid Y$ 时，约分后的 $b,c$ 互质，模方程唯一确定 $j$ 关于 $c$ 的剩余类，所以 $(j_0,k_0)$ 是一个整数解。

二元一次不定方程的任意两个解之差满足 $b\Delta j+c\Delta k=0$。由 $b,c$ 互质可知必存在整数 $t$，使得 $\Delta j=tc$、$\Delta k=-tb$。因此上述参数式不遗漏也不重复任何整数解。

最后，算法仅统计同时满足 $1\le j,k\le N$ 的参数 $t$，所以固定 $i$ 的贡献恰好正确。对所有 $1\le i\le N$ 求和后，每个合法三元组按其唯一的 $i$ 被统计一次，答案正确。

复杂度分析

扩展欧几里得耗时 $O(\log\max(B,C))$；之后每个 $i$ 只做常数次整数运算。总时间复杂度为 $O(N+\log\max(B,C))$，空间复杂度为 $O(1)$。