c++ # 【mx-x5-t2】「gfoi round 1」interstellar ## 题目背景 > [interstellar - pikasonic](https://music.163.com/#/song?id=1900207101) ## 题目描述 你有一个正整数 $x$，你可以对它进行如下操作： - 选择一个正整数 $y$，把 $x$ 变为它的 $\gcd(x, y)$ 倍，即 $x \gets x \times \gcd(x, y)$。 （$\gcd(x, y)$ 表示 $x, y$ 的最大公因数。） $x$ 的初始值为 $n$，你想通过若干次操作（也可不操作）将它变为 $m$。你想知道至少要多少次操作才能达成目标，或报告无解。 ## 输入格式 **本题有多组测试数据。** 第一行输入一个正整数 $t$，表示测试数据组数。 对于每组测试数据： 第一行包含两个正整数 $n, m$。 ## 输出格式 对于每组数据： - 若无解，即 $x$ 无论如何操作都不能变成 $m$，输出 $-1$。 - 否则输出一行一个非负整数，表示最小的操作次数。

以下是使用 C++ 解决此问题的代码： ```cpp #include <iostream> #include <vector> using namespace std; int gcd(int a, int b) { while (b!= 0) { int temp = b; b = a % b; a = temp; } return a; } int solve(int n, int m) { if (m % n!= 0) { return -1; } int count = 0; int num = n; while (num!= m) { for (int y = 1; y <= m; y++) { int newNum = num * gcd(num, y); if (newNum <= m && newNum > num) { num = newNum; count++; break; } } if (num == m) { break; } } return count; } int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; cout << solve(n, m) << endl; } return 0; } ``` [2024-09-28 15:37:18 | AI写代码神器 | 293点数解答]