首先肯定是使用 Burnside 引理求解，不过题目并没有给定环的大小，但是由于大小为 n 的环至少要有 2^n 的美丽值，所以这个 n 只有 \log m 个。
所以可以快乐的枚举环的大小，假设是 n。
那么要求：
\sum_{i = 0}^{n - 1}{f(g_i)}
将环上一个点向转完后的位置连边，会连出 $\gcd(n, i)$ 个环，并且这些环内的颜色必须一样，再满足美丽值之积为 $x$。
**先将 $a_k$ 变为 $a_k^{\frac{n}{\gcd(n, i)}}$。**
此时设 $h(i)$ 表示 $i$ 出现的次数，$dp_{i, j}$ 表示 $i$ 个数乘积为 $j$ 的方案数。
转移为：
$$dp_{i, j} = \sum_{d | j}{h(\frac{j}{d})\times dp_{i - 1, d}}$$
如果设 $F * G$ 表示两者的狄利克雷卷积，就有：
$$dp_i = dp_{i - 1} * h = h^i$$
$x$ 的答案就是 $dp_{\gcd(n, i)}$ 的第 $x$ 项。
这样长度为 $n$ 的答案就是 $\sum_{i = 0}^{n - 1}{h^{\gcd(n, i)}}$。
不过复杂度有点劣，改为枚举 $gcd(n, i)$，答案变成 $\sum_{d | n}{h^d \varphi(\frac{n}{d})}$。
总答案为：
$$\sum_{n = 1}^{\log m}{\sum_{d | n}{h^d \varphi(\frac{n}{d})}}$$
> 注：此处 $h$ 随着 $n$ 和 $d$ 变化。
分析一下复杂度，这两个求和是 $\mathcal{O}(\sqrt{\log m}\log m)$ 的，卷积使用快速幂会进行 $\log{\log m}$ 次卷积，一次卷积是 $\mathcal{O}(m \log m)$ 的。
所以复杂度是 $\mathcal{O}(m\sqrt{\log m}\log^2 m\log{\log m})$ 的，常数比较小。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
#define int long long
#define fi first
#define se second
using pii = pair <int, int>;
int n, m, a[N];
class Poly
{
public :
int f[N];
friend Poly operator * (Poly x, Poly y)
{
Poly res;
for (int i = 1; i <= m; i++) res.f[i] = 0;
for (int i = 1; i <= m; i++)
{
if (!x.f[i]) continue;
for (int j = 1; j <= m / i; j++)
{
(res.f[i * j] += x.f[i] * y.f[j]) %= mod;
}
}
return res;
}
};
Poly qpow(Poly x, int b)
{
Poly res;
for (int i = 1; i <= m; i++) res.f[i] = 0;
res.f[1] = 1;
while (b)
{
if (b & 1) res = res * x;
x = x * x;
b >>= 1;
}
return res;
}
int qpow(int x, int b, int lim)
{
int res = 1;
while (b)
{
if (b & 1)
{
if (x > lim) return false;
res = res * x;
if (res > lim) return false;
}
if (x <= lim) x = x * x;
b >>= 1;
}
return res;
}
int qpow(int x, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * x % mod;
x = x * x % mod;
b >>= 1;
}
return res;
}
int phi(int x)
{
int res = x;
for (int i = 2; i * i <= x; i++)
{
if (x % i) continue;
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x != 1) res = res / x * (x - 1);
return res;
}
int ans[N];
Poly F;
signed main()
{
ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int lim = 0;
while ((1 << lim) <= m) lim++;
for (int _n = 1; _n <= lim; _n++)
{
bool flag = 0;
for (int i = n; i >= 1; i--) if (qpow(a[i], _n, m)) flag = 1;
if (!flag) break;
int inv = qpow(_n, mod - 2);
for (int i = 1; i <= _n; i++)
{
if (_n % i) continue;
for (int j = 1; j <= m; j++) F.f[j] = 0;
for (int j = 1; j <= n; j++) F.f[qpow(a[j], _n / i, m)]++;
Poly tmp = qpow(F, i);
int ph = phi(_n / i);
for (int j = 2; j <= m; j++) (ans[j] += tmp.f[j] * ph % mod * inv) %= mod;
}
}
for (int i = 2; i <= m; i++) cout << ans[i] << ' ';
return 0;
}
```