CF2114F Small Operations 题解

lucasincyber · 2025-11-21 19:01:46 · 题解

题目传送门。

思路

令 d = \gcd(x,y)，a = \displaystyle \frac{x}{d}，b = \displaystyle \frac{y}{d}。易知最少操作次数一定是把 a 先除到 1，再乘到 b。可以将除 a 转化为乘 a 再取倒数。所以问题就变成了 1 通过一直乘若干个 1 \le t \le k 的整数 t，使其变为 a，b 的最小操作次数。

直接用 DP 解决。设 dp_i 代表从 1 到 i 的最小操作次数。则：

所以答案就为 ans = dp_a + dp_b。如果 ans \ge +\infty，则无解。因为需要 1 \sim n 中每一个数的所有因数，所以用 \mathcal{O}(n \log n) 的方法解决。我们会发现，不用枚举 1 \sim n，只用枚举 n 的所有因数即可。

令 n = \max(a,b)时。间复杂度 \mathcal{O}(n \log n + \sum f(n))，其中 f(n) 为 n 的因数个数，在 n \le 10^6 时 f(n)_{\max} \approx 250。可以通过。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, inf = 1e9;

int t, x, y, k;
vector<int> fact[N];
int dp[N];

void init()
{
    for (int i = 1; i < N; i++)
        for (int j = i; j < N; j += i)
            fact[j].push_back(i);
    for (int i = 1; i < N; i++) dp[i] = inf;
}

int calc(int n)
{
    dp[1] = 0;
    for (int i : fact[n])
        for (int j : fact[i])
            if (j <= k) dp[i] = min(dp[i], dp[i / j] + 1);
    int now = dp[n];
    for (int i : fact[n]) dp[i] = inf;
    return now;
}

void solve()
{
    scanf("%d%d%d", &x, &y, &k);
    int d = __gcd(x, y);
    int a = x / d, b = y / d;
    int res = calc(a) + calc(b);
    if (res >= inf) printf("-1\n");
    else printf("%d\n", res);
}

int main()
{
    init();
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}