【题解】P9836

· · 题解

赛时写了个特判想稳部分分，但是发现打挂了痛失 3 分...

可以注意到，每个数的正因子其实就是质因子的不同组合形式。

比如 2 \times 3 \times 3\times 5 = 90，可以发现，所有因数可以如此得到：

每个质因子的数量 2 3 5
1 0 0 0
5 0 0 1
3 0 1 0
15 0 1 1
9 0 2 0
45 0 2 1
2 1 0 0
10 1 0 1
6 1 1 0
30 1 1 1
18 1 2 0
90 1 2 1

可以看出，质因子的数量取决于每个质因子的数量搭配。若第 i 个质因子数量为 a_i，则第 i 个质因子可以有 0-a_i 共 i+1 种选择。根据乘法原理，因子数即为 \prod_{i=1}^{cnt}a_i+1，其中 cnt 为质因子数量。

接下来就是如何存这些数据的问题。由于 1\le p_i \le 10^4，2 \times 3 \times 5\times 7\times11\times13=30030 > 10000 可得一个数不同质因数数量不会超过 6，所以干脆开个结构体存质因数和他们的数量好了。

接下来考虑施肥操作。因为施肥的 k 必须是肥料总量 w 的因数，当然可以想到一样把它质因数分解。给一棵树施 k 单位肥等价于给一棵树施肥 d 次，且每次施肥的乘积等于 k。然后以质因数为单位施肥就好。注意将肥料用完一定最优，因为肥料一定有贡献。

接下来考虑每个数对答案的贡献。一棵树被施肥，即这棵树对应的质因子 +1。对答案的贡献为 \dfrac{a_i+1}{a_i}，显而易见的，当 a_i 最小时贡献最大，所以贪心一下即可。

最后注意不要实时更新答案，因为有 \bmod 操作。操作完在最后统计答案就好。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,w;
ll p[11451];
struct CUN{
    ll pr[30],c[30],cnt;//质因数，每个质因数的数量，不同质因数总数
}z[11451],hf;
ll ans=1;//注意初始化
ll mod=998244353;
int main(){
    scanf("%lld%lld",&n,&w);
    for(ll i=1;i<=n;i++)scanf("%lld",&p[i]);
    ll xd=0;
    ll qwq;
    for(ll i=1;i<=n;i++){
        qwq=p[i];
        for(ll j=2;j*j<=p[i];j++){
            xd=0;
            while(qwq%j==0)xd++,qwq/=j;//质因数分解
            if(xd!=0){
                z[i].pr[++z[i].cnt]=j;
                z[i].c[z[i].cnt]=xd;
            }
            if(qwq==1)break;
        }
        if(qwq!=1){//注意本身是质数情况
            z[i].pr[++z[i].cnt]=qwq;
            z[i].c[z[i].cnt]=1;
        }
    }

    qwq=w;//对化肥数量质因数分解
    for(ll j=2;j*j<=w;j++){
        xd=0;
        while(qwq%j==0)xd++,qwq/=j;
        if(xd!=0){
            hf.pr[++hf.cnt]=j;
            hf.c[hf.cnt]=xd;
        }
        if(qwq==1)break;
    }
    if(qwq!=1){
        hf.pr[++hf.cnt]=qwq;
        hf.c[hf.cnt]=1;
    }

    //可怕的四重循环 但是复杂度不会爆炸哦
    for(ll i=1;i<=hf.cnt;i++){
        ll now=hf.pr[i];
        for(ll j=1;j<=hf.c[i];j++){
            ll minn=0x3f3f3f3f,pos=0;//找最小a[i]
            for(ll k=1;k<=n;k++){
                ll ct=0;
                for(ll x=1;x<=z[k].cnt;x++){
                    if(z[k].pr[x]==now){
                        ct=z[k].c[x];
                        break;
                    }
                }
                if(ct<minn){
                    minn=ct;
                    pos=k;
                }
            }
            if(minn==0){
                z[pos].cnt++;
                z[pos].pr[z[pos].cnt]=now;
                z[pos].c[z[pos].cnt]=1;
            }//出现新的质数
            else for(ll x=1;x<=z[pos].cnt;x++){
                if(z[pos].pr[x]==now){
                    z[pos].c[x]++;
                    break;
                }
            }//原有的质数直接加就行

        }
    }

    for(ll k=1;k<=n;k++){
        for(ll x=1;x<=z[k].cnt;x++){
            ans*=(z[k].c[x]+1);
            ans%=mod;//统计答案
        }
    }
    printf("%lld",ans);//完结撒花
    return 0;
}