题解：CF2114F Small Operations

_std_O2 · 2025-08-29 16:09:45 · 题解

题目描述

给你两个正整数 x,k。进行以下两种变换之一称为一次操作：

• 选择一个满足 1 \le a \le k 的正整数 a，使 x 变为 x\cdot a；
• 选择一个满足 1 \le a \le k 的正整数 a，使 x 变为 \frac{x}{a}，要求操作完后 x 值是整数。

你需要找出使 x 变为给定正整数 y 的最小操作次数，或判断无解。

Sol

考虑先将 x 变为 \gcd(x,y) 再将 \gcd(x,y) 变为 y。显然这样操作所需的次数最少。

先将 \frac{x}{\gcd(x,y)} 和 \frac{y}{\gcd(x,y)} 因数分解，再用 dp 将其凑起来就行。

设 dp_i 为当前因数的乘积为 i 是所需的最小操作次数，dp 的过程就用记忆化搜索就行了。

其中 d(i) 为小于 k 的 i 的因数。

Code

#include<bits/stdc++.h>
using namespace std;
int dp[1000005];
bool check(int x,int k){
    for (int i=2;i*i<=x&&i<=k;i++) while (x%i==0) x/=i;
    return (x<=k);
}

int dfs(int x,int k){
    if(x==1) return 0;
    if(dp[x]) return dp[x];
    if(x<=k){
        dp[x]=1;
        return 1;
    }
    dp[x]=1e9;
    for(int i=k;i>1;i--) if(x%i==0) dp[x]=min(dp[x],dfs(x/i,k)+1);
    return dp[x];
}

int main(){
    int T;
    cin>>T;
    while(T--){
        memset(dp,0,sizeof dp);
        int a,b,k,ans=0;
        cin>>a>>b>>k;
        int fk=__gcd(a,b);
        a=a/fk,b=b/fk;
        if(!check(a,k) || !check(b,k)){
            cout<<-1<<endl;
            continue; 
        }
        cout<<dfs(a,k)+dfs(b,k)<<endl;
    }
}