题解归档 - cf2236F1

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2236F1
• 本地来源：problems/cf2236F1/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/F1
• 原始标题：cf2236F1 — Elections in Saransk (easy)

思路

cf2236F1 — Elections in Saransk (easy)

F2 完整题解见 ../cf2236F/idea.md。本节仅 F1（x=1）。

结论

理想投票 ⟺ 所选 p_i 两两互素 ⟺ 每个素数至多出现在一个 p_i 中。

对素数 pr，设所有 a_i 中该素数指数之和为 S_{pr}，则贡献 1+S_{pr}，总答案

[
\prod_{pr} (1 + S_{pr}).
]

做法

SPF 筛 + 每人分解，对每个素因子把指数累加到 cnt[pr]，答案乘 (cnt[pr]+1)。

样例

代码

来源：problems/cf2236F1/solution.cpp

/* Author: likely
 * Time: 2026-06-19 10:56:48
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=500005;
const ll mod=1000000007;
ll spf[maxn+5],cnt[maxn+5],n,x,i,j,k,ans;
vector<ll>touched;
void init(){
    for(i=2;i<=maxn;i++){
        if(!spf[i]) for(j=i;j<=maxn;j+=i) if(!spf[j]) spf[j]=i;
    }
}
int main(){
    init();
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&x);
        touched.clear();
        for(i=1;i<=n;i++){
            scanf("%lld",&k);
            while(k>1){
                ll p=spf[k],c=0;
                while(k%p==0){
                    k/=p;
                    c++;
                }
                if(!cnt[p]) touched.push_back(p);
                cnt[p]+=c;
            }
        }
        ans=1;
        for(ll p:touched){
            ans=ans*(cnt[p]+1)%mod;
            cnt[p]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}