取模的最小公倍数

题意

给定的 $n$ 个数 $a_i$。

求 $\operatorname{lcm}\left(a_1, a_2, \ldots, a_n\right) \bmod 998244353$。

$1 \leq n \leq 5000, 1 \leq a_i \leq 10^{18}$

题解

我们设

$$f_i = \operatorname{lcm}\left(a_1, a_2, \ldots, a_i\right) = b_1b_2 \cdots b_i$$

其中 $b_i = \frac{a_i}{\gcd\left(b_1b_2 \cdots b_{i - 1}, a_i\right)} \bmod 998244353$，那么就有 $f_i = f_{i - 1} \cdot b_i$。

考虑怎么算 $b_i$。对于 $\gcd\left(b_1b_2 \cdots b_{i - 1}, a_i\right)$，我们可以手动做一次欧几里得，变成 $\gcd\left(b_1b_2 \cdots b_{i - 1} \bmod a_i, a_i\right)$，这样可以 $O\left(n\right)$ 算出来。

总复杂度 $O\left(n^2 + n \log V\right)$。

代码

int WITHERING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
   constexpr tp mod = 998244353;
   tp n; cin >> n;
   vector<tp> a(n);
   vector<tp> b(n);
   for (auto& i : a) cin >> i;
   vector<tp> f(n);
   f[0] = b[0] = a[0];
   for (tp i = 1; i < n; ++i) {
      tp cur = 1;
      for (tp j = 0; j < i; ++j) cur = __int128(cur) * b[j] % a[i];
      b[i] = a[i] / lib::gcd(cur, a[i]);
      f[i] = __int128(f[i - 1]) * b[i] % mod;
   }
   cout << f.back() << '\n';
   return 0;
}