题解归档 - cf2236F

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

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

思路

cf2236F — Elections in Saransk (F1 + F2)

题意

每人带来 a_i，在 a_i 的因子里选一个作为投票 p_i。称投票理想当且仅当

[
x \cdot \mathrm{lcm}(p_1,\ldots,p_n) = p_1 \cdots p_n .
]

求不同数组 p 的个数 mod 1e9+7。F1 固定 x=1；F2 允许 1\le x\le 5\cdot 10^5。

关键转化（按素数独立）

对素数 pr，记 v_{pr}(\cdot) 为指数。条件等价于对每个 pr：

[
\max_i v_{pr}(p_i) + v_{pr}(x) = \sum_i v_{pr}(p_i)
\quad\Leftrightarrow\quad
\sum_i v_{pr}(p_i) - \max_i v_{pr}(p_i) = v_{pr}(x).
]

左边是「除最大指数外其余指数之和」。不同素数互不影响，总答案为各素数贡献之积。

F1（x=1）

此时 v_{pr}(x)=0，故每个素数上至多一人有正指数，且该人指数即为总和。等价于 p_i 两两互素。

对固定素数 pr，在所有人因子分解里收集其指数列表（每人至多出现一次）。贡献为

[
1 + \sum_i v_{pr}(a_i)
]

（1 表示该素数完全不选；否则选某人的某个正指数）。预处理 SPF 筛，按人分解累加指数计数即可。

F2（一般 x）

素数 pr ∤ x

与 F1 相同：贡献 1 + \sum v_{pr}(a_i)。

素数 pr \mid x

设 vp = v_{pr}(x)，第 i 人可选指数 0..v_{pr}(a_i)。DP：

dp[i][mx][s] = 前 i 人，当前最大指数为 mx、指数和为 s 的方案数。

转移枚举第 i 人选 e：

• 若 e \le mx：新和 s+e，最大仍为 mx；
• 若 e > mx：新最大 e，新和 s+e。

该素数答案为 \sum_{mx} dp[n][mx][vp+mx]（需 vp+mx \le 总指数上界）。vp+mx \le 36（因 v_{pr}(a_i)\le 18），可用滚动数组。

若 x 含某素数 pr，但所有 a_i 都不含 pr，则无解（答案 0）。

实现要点

• SPF 线性筛至 5\cdot 10^5。
• 每人分解时把 (pr, exponent) push 到 ex[pr]。
• F2 每个测试清空 ex[pr]，避免跨测污染。
• 提交：F1 → 2236F1，F2 → 2236F2（本目录 solution.cpp 为 F2 完整版，F1 见 cf2236F1/）。

验证

• 样例：F1 8 4 40 64；F2 2 0 360 0 0。
• 小数据暴力：brute.cpp 枚举各 p_i\mid a_i 检查 x·lcm=prod。

代码

来源：problems/cf2236F/solution.cpp

/* Author: likely
 * Time: 2026-06-19 13:03:20
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1000000007;
const ll maxa=500005;
const ll maxn=100005;
ll spf[maxa+5],pr[maxa+5],pcnt,n,x,i,j,k,t,ans,mx,cur,vp,s;
ll p[maxn+5];
map<ll,ll>xcnt,scnt;
map<ll,vector<ll>>w1;
vector<ll>dp[25],nd[25];
void init(){
    for(i=2;i<=maxa;i++){
        if(!spf[i]){
            pcnt++;
            pr[pcnt]=i;
            spf[i]=i;
        }
        for(j=1;j<=pcntandpr[j]<=spf[i]andi*pr[j]<=maxa;j++)
            spf[i*pr[j]]=pr[j];
    }
}
void addprime(ll id,ll c){
    if(c){
        scnt[id]+=c;
        if(xcnt.count(id)) w1[id].push_back(c);
    }
}
void facta(ll v){
    while(v>1){
        ll w=spf[v],c=0;
        while(v%w==0){
            v/=w;
            c++;
        }
        addprime(w,c);
    }
}
ll solveprime(ll id,ll e){
    mx=0;
    for(i=0;i<(ll)w1[id].size();i++) mx=max(mx,w1[id][i]);
    for(i=0;i<=e;i++){
        dp[i].assign(mx+1,0);
        nd[i].assign(mx+1,0);
    }
    dp[0][0]=1;
    for(i=0;i<(ll)w1[id].size();i++){
        k=w1[id][i];
        for(j=0;j<=e;j++) fill(nd[j].begin(),nd[j].end(),0);
        for(cur=0;cur<=k;cur++){
            for(j=0;j<=e;j++){
                for(llmxv=0;mxv<=mx;mxv++){
                    if(!dp[j][mxv]) continue;
                    ll nj=j+min(cur,mxv);
                    if(nj>e) continue;
                    ll nmx=max(cur,mxv);
                    nd[nj][nmx]=(nd[nj][nmx]+dp[j][mxv])%mod;
                }
            }
        }
        for(j=0;j<=e;j++) dp[j]=nd[j];
    }
    cur=0;
    for(i=0;i<=mx;i++) cur=(cur+dp[e][i])%mod;
    return cur;
}
int main(){
    init();
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&x);
        xcnt.clear();
        scnt.clear();
        w1.clear();
        cur=x;
        while(cur>1){
            j=spf[cur];
            while(cur%j==0){
                xcnt[j]++;
                cur/=j;
            }
        }
        if(cur>1) xcnt[cur]++;
        for(i=1;i<=n;i++){
            scanf("%lld",&p[i]);
            facta(p[i]);
        }
        ans=1;
        for(auto&it:scnt){
            j=it.first;
            s=it.second;
            if(!xcnt.count(j) or !xcnt[j]) ans=ans*(s+1)%mod;
            else ans=ans*solveprime(j,xcnt[j])%mod;
        }
        for(auto&it:xcnt){
            if(it.second and !scnt.count(it.first)) ans=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}