CF2114F

DDF_ · 2025-10-05 11:44:50 · 题解

题解

注意到最好的方案是将 a 通过操作转化为 \gcd(a,b) 再将其转化为 b。

证：若转化到低于 \gcd(a,b) 的数，下一步最优肯定要转化到 b 的因数。由于有 k 的限制，所以在合法方案下，在 \gcd(a,b) 上可以一步转化到的一个数 x，在低于 \gcd(a,b) 上需要至少一次操作转化到 x。因此从 \gcd(a,b) 转化不劣。

然后设 x=\frac{a}{\gcd(a,b)}，y=\frac{b}{\gcd(a,b)}，此时 \gcd(x,y)=1，问题转化为将 x 变为 1 再变为 y 的最小操作次数。

可以看作将 x 除到 1 加上将 y 除到 1 的操作次数，前提为除数小于等于 k。

发现如果 x 和 y 中有任意一个，它的最大质因数大于 k，则无解。

其余情况皆有解，用记忆化搜索即可。

用 memset 炸了，考试慎用 memset。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int _;
ll x,y,k;
ll f[N];
inline ll dfs(ll x) {
    if(x==1) return 0;
    if(x<=k) return 1;
    if(f[x]!=-1) return f[x];
    for(int i=k;i>1;i--) {
        if(x%i==0) {
            ll nxt=dfs(x/i);
            if(nxt==-1) continue;
            if(f[x]==-1) f[x]=nxt+1ll;
            else f[x]=min(f[x],nxt+1ll);
        }
    }
    return f[x];
}
inline ll gcd(ll a,ll b) {
    if(!b) return a;
    return gcd(b,a%b);
}
int main() {
    scanf("%d",&_);
    while(_--) {
        scanf("%lld%lld%lld",&x,&y,&k);
        ll g=gcd(x,y);
        ll a=x/g,b=y/g;
        for(int i=1;i<=max(a,b);i++) f[i]=-1;
        if(dfs(a)==-1||dfs(b)==-1) puts("-1");
        else printf("%lld\n",dfs(a)+dfs(b));
    }
    return 0;
}