题解归档 - cf2233F

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

• 本地编号：cf2233F
• 本地来源：problems/cf2233F/idea.md
• 题目链接：https://codeforces.com/contest/2233/problem/F
• 原始标题：cf2233F - Shortest GCD Paths

思路

cf2233F - Shortest GCD Paths

pattern:
factor block replacement / divisor DP

edge meaning:
For an edge between u=g*x and v=g*y with g=gcd(u,v), the cost is
max(x,y). Thus one move replaces a factor block x of the current number by
a factor block y, paying max(x,y).

reduce:
Let g=gcd(a,b), A=a/g, B=b/g. Common factors need not be touched. The
task is to split the factors of A and B into paired blocks
(x_1,y_1),...,(x_k,y_k) with products prod x_i=A, prod y_i=B, minimizing
sum max(x_i,y_i).

bound:
Any such block sequence can be ordered so intermediate values do not exceed
max(a,b): first apply blocks with y_i<=x_i, then blocks with y_i>x_i.
The first phase only decreases; in the second phase every partial product is at
most the final product of that phase. Since a,b<=n, the graph bound is not a
separate restriction.

DP:
dp(x,y) is the minimum cost to replace remaining product x by y. If
x>1, choose a nontrivial divisor dx|x and any dy|y, pay max(dx,dy),
and recurse to (x/dx,y/dy). If x==1, split the remaining y into divisor
blocks. Divisor counts for numbers up to 1e9 are small, so memoized recursion
is fast.

check:
brute.cpp runs Dijkstra on the complete graph for small n.

代码

来源：problems/cf2233F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> divA,divB;
unordered_map<unsigned long long,ll> memo;
vector<ll> getDivs(ll x){
    vector<ll>d;
    for(ll i=1;i*i<=x;i++){
        if(x%i==0){
            d.push_back(i);
            if(i*i!=x) d.push_back(x/i);
        }
    }
    sort(d.begin(),d.end());
    return d;
}
ll dp(ll x,ll y){
    if(x==1 and y==1) return 0;
    unsigned long long key=((unsigned long long)x<<32)^(unsigned long long)y;
    auto it=memo.find(key);
    if(it!=memo.end()) return it->second;
    ll best=max(x,y);
    if(x>1){
        for(ll dx:divA){
            if(dx<=1 or x%dx) continue;
            for(ll dy:divB){
                if(y%dy) continue;
                best=min(best,max(dx,dy)+dp(x/dx,y/dy));
            }
        }
    }else{
        for(ll dy:divB){
            if(dy<=1 or y%dy) continue;
            best=min(best,dy+dp(1,y/dy));
        }
    }
    memo[key]=best;
    return best;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,a,b;
    cin>>n>>a>>b;
    ll g=gcd(a,b);
    a/=g;
    b/=g;
    divA=getDivs(a);
    divB=getDivs(b);
    cout<<dp(a,b)<<"\n";
    return 0;
}