题解：CF1033D Divisors

fish_love_cat · 2025-07-21 13:42:30 · 题解

看到题，直接分解质因数然后丢 map 里不就做完了？

值域这么大，Pollard-rho 就好了啊！

做完了。

常数挂爆了。膜拜楼下卡常大神，我菜完了 /kk

急需更优秀的做法。

注意到：

每个 a_i 的约数个数在 3 到 5 之间。

分类讨论一下。

设 a_i 的约数数量为 d：

• 当 d=3，显然 a_i 是质数的平方。
• 当 d=5，显然 a_i 是质数的四次方。
• 当 d=4，显然 a_i 是质数的三次方或两个质数的积。

如果只有一个质因子，可以直接算。

两个质因子直接筛或者 Pollard-rho 都容易爆，我们需要充分发扬人类智慧。

根据数学直觉，我们发现如果数列中与其不同的数字全部与其互质，那么它的两个质因子出现总数就是这个数字的出现次数。

此时一样可以计数。

否则利用它们的 \gcd 即可分解质因数。

做完了。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
map<int,int>mp;
map<int,int>pm;
int a[505];
int ans=1;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        int x=a[i];
        if(x==1)continue;
        int qwq=cbrt(x);
        if(qwq*qwq*qwq==x){
            mp[qwq]+=3;
            continue;
        }
        int flc=sqrt(x);
        if(flc*flc==x){
            int clf=sqrt(flc);
            if(clf*clf==flc)mp[clf]+=4;
            else mp[flc]+=2;
        }else{
            int qwq=0;
            for(int j=1;j<=n;j++){
                qwq=__gcd(a[i],a[j]);
                if(qwq!=1&&qwq!=a[i])break;
            }
            if(qwq!=1&&qwq!=a[i])mp[x/qwq]++,mp[qwq]++;
            else pm[a[i]]++;
        }
    }
    for(auto i:mp)
    ans=ans*(i.second+1)%mod;
        // cout<<i.first<<' '<<i.second<<'\n';
    for(auto i:pm)
    ans=ans*(i.second+1)%mod*(i.second+1)%mod;
        // cout<<i.first<<' '<<i.second<<'\n';
    cout<<ans;
    return 0;
}