# 【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$。 - 否则输出一行一个非负整数，表示最小的操作次数。 ##

以下是使用 Python 解决此问题的代码： ```python import math def gcd(a, b): while b!= 0: a, b = b, a % b return a def solve(n, m): if m % n!= 0: return -1 count = 0 while n < m: for y in range(1, m + 1): new_n = n * gcd(n, y) if new_n > n and new_n <= m: n = new_n count += 1 break else: return -1 return count t = int(input()) for _ in range(t): n, m = map(int, input().split()) print(solve(n, m)) ``` 这段代码首先定义了一个求最大公因数的函数`gcd`，然后定义了`solve`函数来计算将`n`通过操作变为`m`所需的最少操作次数。在主程序中，读取测试数据的组数`t`，然后对每组数据调用`solve`函数并输出结果。 [2024-09-28 15:36:37 | AI写代码神器 | 256点数解答]