题目分析
给定 \(n\) 个正整数 \(a_1,a_2,\dots,a_n\) 和 \(n\) 个正整数 \(b_1,b_2,\dots,b_n\)，计算每对 \((i,j)\)，\(a_i\) 与 \(b_j\) 的最大公因数，并输出
\[A_i = \sum_{j=1}^{n} i^j \cdot \gcd(a_i, b_j)
\]
的计算结果。
关键点
- \(n \leq 5000\)，直接计算所有 \(n^2\) 对辗转相除法和朴素更相减损术求 \(\gcd\) 是 \(O(n^2 \log \text{max})\) 的复杂度。
- \(a_i, b_i \leq 10^6\)，\(\log \text{max}\) \(\approx\) \(20\)，会被卡常。
解题思路
方法分析
由于 \(n\) 最大为 \(5000\)，\(n^2 = 25 \times 10^6\)，如果我们能在 \(O(1)\) 或近似 \(O(1)\) 的时间内计算 \(\gcd\)，那么总计算量大约为 \(2.5 \times 10^7\) 次运算，可以接受。
优化
原理
更相减损术可以使用二进制除法进行优化，当 \(a\) 和 \(b\) 同时为偶数的时候，它们的二进制表示一定有一段相同的后缀 \(0\)，计算这个后缀 \(0\) 的长度，分别对 \(a\) 和 \(b\) 进行右移位运算，可以使得至少一个参数变成奇数，然后直接进行下一步的更相减损运算，避免了多次递归除以 \(2\)。
实现步骤
- 如果 \(a\) 或 \(b\) 为 \(0\)，返回另一个数。
- 移除 \(a\) 和 \(b\) 的所有因子 \(2\)，记录移除的个数。
- 使用更相减损术：始终保持 \(a \geq b\)，然后用差值替换较大的数。
- 直到其中一个为 \(0\)，返回另一个数左移之前记录的因子 \(2\) 的个数。
时间复杂度
注：__builtin_ctz() 的时间复杂度是 \(O(1)\)。
- 总时间复杂度：\(O(n^2 \cdot \log \min(a, b))\)。
- 总操作数约 \(5 \times 10^8\)，勉强可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;
long long MOD = 998244353;
typedef long long ll;
ll n, x[5010], y[5010];// 更相减损术(二进制除法)
ll gcd(ll a, ll b) {int ctza = __builtin_ctz(a);//a二进制的后缀0个数int ctzb = __builtin_ctz(b);//b二进制的后缀0个数int ctz = min(ctza, ctzb);//a和b的公共后缀0的个数ll d;//差b >>= ctzb;while (a) {a >>= ctza;d = b - a;// 计算差值ctza = __builtin_ctz(d);// 更新ctza为差值的因子2的个数if (a < b) b = a;// 更新a和b：总让b成为较小的数if (d < 0) a = -d;elsea = d;}return b << ctz;// 返回结果：b左移ctz位（恢复之前移除的因子2）
}int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> x[i];for (int i = 1; i <= n; i++)cin >> y[i];for (int i = 1; i <= n; i++) {ll ans = 0, d = i;for (int j = 1; j <= n; j++) {ans = (ans + d * gcd(x[i], y[j])) % MOD;d = (d * i) % MOD;}cout << ans << endl;}return 0;
}