专栏文章

CF2114F Small Operations 题解

llucasincyber
CF2114F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3hd6v
此快照首次捕获于
2025/12/01 19:57
3 个月前
此快照最后确认于
2025/12/01 19:57
3 个月前
查看原文
题目传送门。

思路

令 d=gcd⁡(x,y)d = \gcd(x,y)，a=xda = \displaystyle \frac{x}{d}，b=ydb = \displaystyle \frac{y}{d}。易知最少操作次数一定是把 aa 先除到 11，再乘到 bb。可以将除 aa 转化为乘 aa 再取倒数。所以问题就变成了 11 通过一直乘若干个 1≤t≤k1 \le t \le k 的整数 tt，使其变为 aa，bb 的最小操作次数。
直接用 DP 解决。设 dpidp_i 代表从 11 到 ii 的最小操作次数。则：
dpi=min⁡j∣i,1≤j≤k(dpij+1)dp_i = \min_{j | i, 1 \le j \le k} (dp_{\frac{i}{j}} + 1)
所以答案就为 ans=dpa+dpbans = dp_a + dp_b。如果 ans≥+∞ans \ge +\infty，则无解。因为需要 1∼n1 \sim n 中每一个数的所有因数，所以用 O(nlog⁡n)\mathcal{O}(n \log n) 的方法解决。我们会发现，不用枚举 1∼n1 \sim n，只用枚举 nn 的所有因数即可。
令 n=max⁡(a,b)n = \max(a,b)时。间复杂度 O(nlog⁡n+∑f(n))\mathcal{O}(n \log n + \sum f(n))，其中 f(n)f(n) 为 nn 的因数个数，在 n≤106n \le 10^6 时 f(n)max⁡≈250f(n)_{\max} \approx 250。可以通过。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...