题解归档 - cf498C

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

• 本地编号：cf498C
• 本地来源：problems/cf498C/idea.md
• 题目链接：https://codeforces.com/contest/498/problem/C
• 原始标题：CF498C Array and Operations

思路

CF498C Array and Operations

题意

给定长度 n 的数组与 m 个好对 (i,j)（i<j 且 i+j 为奇数）。一次操作选好对并取 v>1 同时整除两端，将两端都除以 v。同一对可重复使用。求最多操作次数。

关键观察

1. 每次只除一个质因子：若一次除以合数 v，等价于连续若干次除以质因子，操作次数不会更多。
2. 不同质因子独立：对质数 p 的操作只影响各位置的 p 的指数，彼此可加。
3. 好对构成二分图：i+j 为奇数 ⟹ 一端下标奇、一端偶。边只在奇偶位置之间。

建模（单质数）

对固定质数 p，记位置 i 的指数为 e_i。

• 源点 S 连向所有奇下标且 e_i>0 的点，容量 e_i。
• 所有偶下标且 e_i>0 的点连向汇点 T，容量 e_i。
• 每个好对 (u,v) 在奇→偶方向连容量 INF 的边。

一次 S→i→j→T 的流量对应一次对 (i,j) 同时消去一个 p。

答案 = 所有质数上的最大流之和。

实现

• 分解 a[i]，用 map 聚合 (位置, 指数)。
• Dinic 模板见 lib/图论(Dinic最大流).cpp 风格（本题费用为 0，普通最大流即可）。
• 建图前先设 tot 再 clear 邻接表，避免首质数时未清空残留边。

复杂度

• 质因子总数 O(n log A)，A≤10^9。
• 单次流 O(V^2 E)，本题 V≤102, E≤O(m)，足够。

样例

8 12 8，好对 (1,2),(2,3)：仅质数 2 贡献流 2，其余为 0。

代码

来源：problems/cf498C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:26:58
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=305,INF=1e18;
struct edge{ll to,cap,rev;};
vector<edge>g[maxn];
ll n,m,i,j,k,u,v,ss,tt,tot,ans,flow;
ll s[maxn],xa[maxn],ya[maxn],zc[maxn],level[maxn],cur[maxn];
map<ll,vector<pair<ll,ll>>>cccc;
void add(ll x,ll y,ll cap){
    g[x].push_back({y,cap,(ll)g[y].size()});
    g[y].push_back({x,0,(ll)g[x].size()-1});
}
bool bfs(){
    ll i,h=0,tl=1,q[maxn+5];
    for(i=0;i<=tot;i++) level[i]=-1,cur[i]=0;
    level[ss]=0,q[0]=ss;
    while(h<tl){
        u=q[h++];
        for(i=0;i<(ll)g[u].size();i++){
            edge e=g[u][i];
            if(e.cap>0 and level[e.to]==-1){
                level[e.to]=level[u]+1;
                q[tl++]=e.to;
            }
        }
    }
    return level[tt]!=-1;
}
ll dfs(ll u,ll aug){
    ll i,v,fl=0;
    if(u==tt) return aug;
    for(i=cur[u];i<(ll)g[u].size();i++){
        cur[u]=i;
        edge e=g[u][i];
        if(e.cap>0 and level[e.to]==level[u]+1){
            v=dfs(e.to,min(aug,e.cap));
            if(v>0){
                g[u][i].cap-=v;
                g[e.to][e.rev].cap+=v;
                fl+=v;
                aug-=v;
                if(aug==0) break;
            }
        }
    }
    return fl;
}
ll dinic(){
    ll zc=0,aug;
    while(bfs()){
        while((aug=dfs(ss,INF))>0) zc+=aug;
    }
    return zc;
}
void fact(ll x,ll id){
    ll p;
    for(p=2;p*p<=x;p++){
        if(x%p==0){
            ll cnt=0;
            while(x%p==0) x/=p,cnt++;
            cccc[p].push_back({id,cnt});
        }
    }
    if(x>1) cccc[x].push_back({id,1});
}
int main(){
    ans=0;
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>s[i];
    for(i=1;i<=m;i++) cin>>xa[i]>>ya[i];
    for(i=1;i<=n;i++) fact(s[i],i);
    for(auto&kv:cccc){
        vector<pair<ll,ll>> &vec=kv.second;
        ss=0;
        tt=n+1;
        tot=tt;
        for(i=0;i<=tot;i++) g[i].clear();
        for(i=0;i<(ll)vec.size();i++){
            u=vec[i].first;
            v=vec[i].second;
            if(u%2==1) add(ss,u,v);
            else add(u,tt,v);
        }
        for(i=1;i<=m;i++){
            u=xa[i],v=ya[i];
            if(u%2==1) add(u,v,INF);
            else add(v,u,INF);
        }
        ans+=dinic();
    }
    cout<<ans<<"\n";
    return 0;
}