Cyclic GCDs

· · 题解

2025-2-15 Update：修改了一处错误。

抽象的证明，美妙的公式，好一道数学题。

首先，对整个序列划分轮换，不就是把分为 k 个不交集合吗？

其次，要求每个集合中的最小值，不就等于将序列从小到大排序后取划分左端点吗？

如此，我们考虑一个函数 F_{i,j} 表示前 i 个数划分为 j 个集合的价值之积的和，则 F_{n, i} = b_i = \sum f(p)，有如下式子：

F_{i,j} = a_i \times F_{i-1,j-1} + (i - 1) \times F_{i-1,j}

这个式子和斯特林数十分相似，我们考虑引入 G_i(x) = \sum\limits_{j = 0}^n F_{i,j}x^j 这个生成函数。

明显的，我们可以使用形式幂级数代换原递推式得到：

[x^j]G_i(x) = [x^{j-1}]a_iG_{i-1}(x) + [x^{j}](i - 1)G_{i-1}(x)

根据幂形式的性质，给 j-1 次项乘上 x 可以得到等幂式，又可以缩回我们的生成函数，即：

\begin{aligned} G_i(x) &= a_ixG_{i-1}(x) + (i - 1)G_{i-1}(x)\\ &= (a_ix + i - 1)G_{i-1}(x) \end{aligned}

而 G_n(x) 便是我们需要求得的 n 元 j 次划分贡献的生成函数。

于是我们有：

\begin{aligned} G_n(x) &= (a_nx + n - 1)G_{n-1}(x)\\ &= (a_nx + n - 1)(a_{n-1}x + n - 2)G_{n-2}(x)\\ &= (a_nx + n - 1)(a_{n-1}x + n - 2)...(a_2x - 1)a_1\\ &= \prod_{i = 1}^n (a_ix + i - 1) \end{aligned}

而 b_i = [x^i]G_n(x)，我们想求 \gcd(b_1,b_2,...,b_n) = \gcd\limits_{i = 1}^n [x^i]G_n(x)，很自然的联想到在 G_n(x) 上下手。

设 m = \gcd\limits_{i = 1}^n [x^i]G_n(x)。

我们考虑将其因式分解，有 G_n(x) = m(c_1x + d_1)(c_2x + d_2)...(c_nx + d_n)。

对于任一 [x^i]G_n(x)，我们总能得到 m \times P，P 为不能再分解的因式，因此我们得到 \gcd(b_1,b_2,...,b_n) = m。

而根据 m = \prod\limits_{i=1}^n \gcd(a_i, i - 1)，我们得出结论：

\gcd(b_1,b_2,...,b_n) = \prod\limits_{i=1}^n \gcd(a_i, i - 1) 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
int n, a[N], ans = 1;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++ ) ans = 1ll * ans * __gcd(a[i], i - 1) % mod;
    cout << ans;
    return 0;
}