洛谷 NOIP 2023 模拟赛 种树

洛谷 NOIP 2023 模拟赛 种树"/>

洛谷 NOIP 2023 模拟赛 种树

洛谷 NOIP 2023 模拟赛 种树

题目大意

路边有 n n n棵树，第 i i i棵树的高度为 a i a_i ai​。

定义这棵树的宽度为它高度的正因数个数，这些树能覆盖的距离为它们宽度的乘积。

你有 w w w个单位的化肥，你可以施若干次肥，每次你可以使用 k k k个单位的化肥（要求 k k k必须为当前化肥量的正因数），让任意一棵树的高度乘上 k k k，同时你剩余的化肥量也会除以 k k k。

求施完化肥后这些树所能覆盖的距离的最大值。输出答案模 998244353 998244353 998244353后的值。

1 ≤ n ≤ 1 0 4 , 1 ≤ a i ≤ 1 0 4 , 1 ≤ w ≤ 1 0 4 1\leq n\leq 10^4,1\leq a_i\leq 10^4,1\leq w\leq 10^4 1≤n≤104,1≤ai​≤104,1≤w≤104

题解

我们先考虑在不施化肥的情况下这些树能覆盖的距离。对于每个 a i a_i ai​，我们将其质因数分解为 p 1 α 1 p 2 α 2 ⋯ p k α k p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} p1α1​​p2α2​​⋯pkαk​​，则第 i i i棵树的宽度为 ( α 1 + 1 ) ( α 2 + 1 ) ⋯ ( α k + 1 ) (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1) (α1​+1)(α2​+1)⋯(αk​+1)，这些树能覆盖的距离就是所有树的宽度的乘积。

将 w w w进行质因数分解，对于 w w w每个质因数 p p p，我们考虑如果将 p p p乘在 a i a_i ai​上，对答案的贡献是多少。如果 a i a_i ai​中 p p p的次数为 k k k，则对答案的贡献为 × k + 2 k + 1 \times \dfrac{k+2}{k+1} ×k+1k+2​。

那么，对于 w w w的每个质因数 p p p，设 w w w中 p p p的次数为 t t t，我们按 a i a_i ai​中 p p p的次数为顺序用小根堆来维护这些树，每次取出 p p p的次数最小的 a i a_i ai​，将其乘上 p p p，计算完对答案的贡献之后将次数加一再放回小根堆中，操作 t t t次。

这样即可得出最优的结果。

时间复杂度为 O ( n log ⁡ v + n log ⁡ n log ⁡ w ) O(n\log v+n\log n\log w) O(nlogv+nlognlogw)，其中 v v v为 a i a_i ai​的值域。

code

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
const long long mod=998244353;
int n,w,a[N+5];
long long ans=1;
priority_queue<int>qt;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void gt(int x){for(int i=2;i*i<=x;i++){if(x%i==0){int q=0;while(x%i==0){x/=i;++q;}ans=ans*(q+1)%mod;}}if(x>1) ans=ans*2%mod;
}
void solve(int p,int q){while(!qt.empty()) qt.pop();for(int i=1;i<=n;i++){int vt=a[i],ct=0;while(vt%p==0){vt/=p;++ct;}qt.push(-ct);}for(int i=1;i<=q;i++){int tmp=-qt.top();qt.pop();ans=ans*mi(tmp+1,mod-2)%mod*(tmp+2)%mod;qt.push(-(tmp+1));}
}
int main()
{scanf("%d%d",&n,&w);for(int i=1;i<=n;i++){scanf("%d",&a[i]);gt(a[i]);}for(int i=2;i*i<=w;i++){if(w%i==0){int q=0;while(w%i==0){++q;w/=i;}solve(i,q);}}if(w>1) solve(w,1);printf("%lld",ans);return 0;
}