专栏文章

题解：CF1033D Divisors

ffish_love_cat
CF1033D题解参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miot8y16
此快照首次捕获于
2025/12/03 00:46
3 个月前
此快照最后确认于
2025/12/03 00:46
3 个月前
查看原文
看到题，直接分解质因数然后丢 map 里不就做完了？
值域这么大，Pollard-rho 就好了啊！
做完了。
常数挂爆了。膜拜楼下卡常大神，我菜完了 /kk
急需更优秀的做法。
注意到：
每个 aia_i 的约数个数在 33 到 55 之间。
分类讨论一下。
设 aia_i 的约数数量为 dd：
  • 当 d=3d=3，显然 aia_i 是质数的平方。
  • 当 d=5d=5，显然 aia_i 是质数的四次方。
  • 当 d=4d=4，显然 aia_i 是质数的三次方或两个质数的积。
如果只有一个质因子，可以直接算。
两个质因子直接筛或者 Pollard-rho 都容易爆，我们需要充分发扬人类智慧。
根据数学直觉，我们发现如果数列中与其不同的数字全部与其互质，那么它的两个质因子出现总数就是这个数字的出现次数。
此时一样可以计数。
否则利用它们的 gcd⁡\gcd 即可分解质因数。
做完了。
CPP
#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;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...