很好的题。
下文令 \(k\) 为原题面中的 \(n\)，\(n\) 为原题面中的 \(k\)，\(m\) 为原题面中的 \(m\)。
从一些简单的情况入手。
1. \(m\) 为质数
- \(k = 0\) 的情况是平凡的，只需要要求 \(\exists i \in [1, n], a_i = 0\) 即可。总方案数减去不合法方案数，答案为 \(m^n - (m - 1)^n\)。
- \(k \ne 0\) 时，我们发现，\(a_{1 \sim n - 1}\) 可以任取，让 \(a_n\) 取 \(\frac{k}{\prod\limits_{i = 1}^{n - 1} a_i}\)，所以 \(a_{1 \sim n - 1}\) 唯一对应一个 \(a_n\)。因此方案数为 \((m - 1)^{n - 1}\)。
2. \(m = p^e\)，其中 \(p\) 为质数，\(e\) 为正整数
仍然特判掉 \(k = 0\)。设 \(k = r \times p^x\)，其中 \(x < e, \gcd(r, p) = 1\)。我们需要把 \(x\) 个 \(p\) 分配到 \(a_{1 \sim n}\)，方案数为 \(\binom{x + n - 1}{n - 1} = \binom{x + n - 1}{x}\)，然后接下来 \(a_{1 \sim n - 1}\) 都可以任取与 \(p\) 互质的数，同样的它们唯一对应一个 \(a_n\)。因此方案数为 \(\binom{x + n - 1}{x} \times (m - \frac{m}{p})^{n - 1}\)。
3. 一般情况
考虑对 \(m\) 进行质因数分解，设 \(m = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_c^{e_c}\)。那么我们可以对每个质因数分别处理，根据 CRT 合并答案，也就是乘起来。接下来转化成了 \(2\) 的情况。但是有一点比较尴尬，就是 \(k = r \times p^x\) 中，\(x\) 可能 \(\ge e\)。此时就相当于 \(p_e \mid \prod\limits_{i = 1}^n a_i\)，因此我们可以把任意 \(\ge e\) 个 \(p\) 分配到 \(a_{1 \sim n}\) 中，考虑容斥，总方案数减去分配的 \(p\) 的个数 \(< e\) 的方案数即可。枚举分配 \(p\) 的个数 \(c = [0, e - 1]\)，也转化成了 \(2\) 的情况。但是注意此时的计算中，\(k = r \times p^x\) 中的 \(r\) 是不确定的，因此还要乘上 \(r\) 的方案数。
code
// Problem: Ex - Product Modulo 2
// Contest: AtCoder - AtCoder Beginner Contest 245
// URL: https://atcoder.jp/contests/abc245/tasks/abc245_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
b %= mod;
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, K;
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
ll res = 1;
for (ll i = n; i >= n - m + 1; --i) {
res = res * i % mod;
}
for (ll i = 1; i <= m; ++i) {
res = res * qpow(i, mod - 2) % mod;
}
return res;
}
}
void solve() {
scanf("%lld%lld%lld", &n, &K, &m);
map<ll, ll> mp;
for (ll i = 2; i * i <= m; ++i) {
if (m % i == 0) {
while (m % i == 0) {
m /= i;
++mp[i];
}
}
}
if (m > 1) {
++mp[m];
}
ll ans = 1;
for (auto p : mp) {
ll m = 1;
for (int _ = 0; _ < p.scd; ++_) {
m *= p.fst;
}
ll k = K % m;
if (k) {
ll c = 0;
while (k % p.fst == 0) {
++c;
k /= p.fst;
}
ll coef = C(c + n - 1, c), t = m - m / p.fst;
ans = ans * coef % mod * qpow(t, n - 1) % mod;
} else {
ll res = qpow(m, n);
for (int c = 0; c < p.scd; ++c) {
ll coef = C(c + n - 1, c), t = m - m / p.fst;
res = (res - coef * qpow(t, n - 1) % mod * (qpow(p.fst, p.scd - c) - qpow(p.fst, p.scd - c - 1) + mod) % mod + mod) % mod;
}
ans = ans * res % mod;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}