题解归档 - cf2236F2

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

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

思路

cf2236F2 Elections in Saransk (hard)

题意

每人从 $a_i$ 的约数中选 $p_i$，求理想投票方案数，满足
$$x\cdot \mathrm{lcm}(p_1,\ldots,p_n)=p_1\cdots p_n \pmod{10^9+7}$$

与 F1 区别：$1\le x\le 5\cdot 10^5$（F1 固定 $x=1$）。

按素数独立

对素数 $pr$，记 $v_i=v_{pr}(p_i)$，$vp=v_{pr}(x)$，条件等价于
$$\sum v_i - \max v_i = vp.$$

各素数互不影响，答案为各素数贡献之积。

两类素数

1. $vp=0$（$pr\nmid x$）：至多一人对该素数取正指数，与 F1 相同，贡献 $1+\sum_i v_{pr}(a_i)$。

2. $vp>0$：对限制 $0\le v_i\le v_{pr}(a_i)$ 做 DP。状态 $(mx,d)$，$mx=\max v$，$d=\sum v-mx$（单调不降，故 $d\le vp$）。转移：

   • 取 $v=0$：不变
   • $v\le mx$：$(mx,d)\to(mx,d+v)$
   • $v>mx$：$(mx,d)\to(v,mx+d)$
     该素数答案为 $\sum_{mx} dp[mx][vp]$。

实现要点

• 线性筛 spf，先分解 $x$ 得目标指数，再分解每个 $a_i$ 累加 cnt 与 pm[p][i]。
• 只对 $x$ 的素因子跑 DP（至多约 7 个），其余素因子用公式。
• $d$ 维上界为 $vp\le 18$，总复杂度可接受。

样例

官方样例第三组经本地暴力枚举为 32（与 DP 一致）。

lib_target

纯数论计数 + 小维 DP，未新增 lib/ 模板。

代码

来源：problems/cf2236F2/solution.cpp

/* Author: likely
 * Time: 2026-06-19 13:10:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=500005;
const ll mod=1000000007;
const ll maxs=40;
ll spf[maxn+5],a[maxn+5],cap[maxn+5],dp[maxs+5][maxs+5],ndp[maxs+5][maxs+5],sm[maxn+5];
ll pr[maxn+5],vx[maxn+5],n,x,i,j,k,pd,zc,mx,ans,cur,vp,t,ec,pc;
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;
    }
}
ll solvePrime(){
    for(i=0;i<=maxs;i++)for(j=0;j<=maxs;j++) dp[i][j]=0;
    dp[0][0]=1;
    for(i=1;i<=n;i++){
        for(j=0;j<=maxs;j++)for(k=0;k<=maxs;k++) ndp[j][k]=0;
        for(pd=0;pd<=cap[i];pd++){
            for(j=0;j<=maxs;j++){
                for(k=0;k<=maxs;k++){
                    if(!dp[j][k]) continue;
                    zc=k+pd;
                    if(zc>maxs) continue;
                    mx=j;
                    if(pd>mx) mx=pd;
                    ndp[mx][zc]+=dp[j][k];
                    if(ndp[mx][zc]>=mod) ndp[mx][zc]-=mod;
                }
            }
        }
        for(j=0;j<=maxs;j++)for(k=0;k<=maxs;k++) dp[j][k]=ndp[j][k];
    }
    ll res=0;
    for(j=0;j<=maxs;j++){
        k=vp+j;
        if(k>maxs) continue;
        res+=dp[j][k];
        if(res>=mod) res-=mod;
    }
    return res;
}
int main(){
    init();
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&x);
        ans=1;
        pc=0;
        cur=x;
        while(cur>1){
            k=spf[cur];
            zc=0;
            while(cur%k==0){
                cur/=k;
                zc++;
            }
            pr[++pc]=k;
            vx[pc]=zc;
        }
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(ec=1;ec<=pc;ec++){
            k=pr[ec];
            vp=vx[ec];
            pd=0;
            for(i=1;i<=n;i++){
                cur=a[i];
                zc=0;
                while(cur%k==0){
                    cur/=k;
                    zc++;
                }
                cap[i]=zc;
                pd+=zc;
            }
            if(!vp){
                ans=ans*(pd+1)%mod;
                continue;
            }
            ll ways=solvePrime();
            ans=ans*ways%mod;
        }
        touched.clear();
        for(i=1;i<=n;i++){
            cur=a[i];
            while(cur>1){
                k=spf[cur];
                zc=0;
                while(cur%k==0){
                    cur/=k;
                    zc++;
                }
                if(!sm[k]) touched.push_back(k);
                sm[k]+=zc;
            }
        }
        for(ll p:touched){
            pd=0;
            for(ec=1;ec<=pc;ec++) if(pr[ec]==p) pd=1;
            if(!pd) ans=ans*(sm[p]+1)%mod;
            sm[p]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}