自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 22:52:16，当前版本为作者最后更新于2023-11-11 19:42:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看到因数个数，想到在质因数分解后的序列上考虑问题。进一步观察，每个不同质因子的贡献是独立的。

也就是说，我们单独考虑某一个质因子对答案的贡献，是这样的问题：

给长度为 $n$ 的序列 $a$ 和一个数 $w$，每次操作你可以选择一个 $i$，令 $a_i\gets a_i+1$，可以重复选择同一个位置。至多操作 $w$ 次，最大化 $\prod\limits_{i=1}^n a_i$。

这是一个经典问题，容易证明每次贪心操作最小值是最优的。数据范围放了 $O(n^2)$ 通过，所以怎么实现都行。

#define int long long
const int N=1e4+5,mod=998244353;
int n,w;
int a[N],cnt[N],ans=1;
priority_queue<int,vector<int>,greater<int> >q;
il void solve(int x,int sum)
{
    for(int i=1;i<=n;i++)
    {
        cnt[i]=1;
        while(a[i]%x==0) cnt[i]++,a[i]/=x;
        q.push(cnt[i]);
    }
    while(sum) 
    {
        int x=q.top(); q.pop();
        q.push(x+1),sum--;
    }
    for(int i=1;i<=n;i++) ans=ans*q.top()%mod,q.pop();
}
signed main()
{
    n=read(),w=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i*i<=w;i++) 
        if(w%i==0)
        {
            int now=0;
            while(w%i==0) now++,w/=i;
            solve(i,now);
        }
    if(w>1) solve(w,1);
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j*j<=a[i];j++)
        {
            int now=1;
            while(a[i]%j==0) a[i]/=j,now++;
            ans=ans*now%mod;
        }
        if(a[i]>1) ans=ans*2%mod;
    }
    printf("%lld\n",ans);
    return 0;
}