提高组模拟赛 50 B. 种树 题解
原题
题目中的 \(p_i\) 在下文为避免歧义均称为 \(a_i\)。
\(a_i\) 和 \(w\) 都可以拆为质因数的形式来处理，即：
\[w=\prod p_k^{c_k}
\]
对于因数个数，有公式
\[sum=\prod_{i=1}^k (c_k+1)
\]
对于 \(a_i\)，乘上一个质数 \(b\) 后，答案会增加
\[\frac{\prod_{i=1}^k (c_k+1)}{c^b+1}
\]
对于这个东西直接通过优先队列贪心维护即可，复杂度 \(O(n\sqrt n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define eb emplace_back
#define mst(x, y) memset(x, y, sizeof(x))
#define pii pair<ll,ll>
#define fi first
#define se second
ll rd() {ll f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}return f*x;}
void writ(ll x) {if(x<0){x=-x;putchar('-');}if(x>9)writ(x/10);putchar(x%10+'0');}
void wr(ll x) {writ(x);puts("");}
void wr_(ll x) {writ(x);putchar(' ');}
const ll N = 1e4+5, inf = 0x3f3f3f3f, M = 998244353;ll n, w, ans;
ll p[N], v[N], g[N];
int f[N][N];void calc(ll x, ll id) {ll res = 0;for(ll i = 1; i*i <= x; i++) if(x%i == 0) res += 2-(x/i==i);g[id] = res;for(ll i = 2; i <= x; i++) {while(x%i == 0) {f[id][i]++;x /= i;}}
}
void solve() {n = rd(), w = rd(), ans = 1;ll ww = w;for(ll i = 2; i <= w; i++) {while(w%i == 0) {v[i]++;w /= i;}}w = ww;for(ll i = 1; i <= n; i++) {p[i] = rd();calc(p[i], i);}for(ll i = 2; i <= w; i++) {if(!v[i]) continue;priority_queue <pii> q;for(ll j = 1; j <= n; j++) q.push({-(f[j][i]+1), j});for(ll j = 1; j <= v[i]; j++) {auto [v, x] = q.top(); q.pop();v = -v;g[x] = g[x]/v*(v+1);q.push({-(v+1), x});}}for(ll i = 1; i <= n; i++) ans = ans*g[i]%M;wr(ans);
}signed main() {// freopen("plant.in", "r", stdin);// freopen("plant.out", "w", stdout);ll T = 1;while(T--) solve();return 0;
}