自动搬运

查看原文

来自洛谷，原作者为

	what_can_I_do **

搬运于2025-08-24 23:04:30，当前版本为作者最后更新于2024-09-29 22:14:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

首先，如果 $m$ 不是 $n$ 的倍数的话，那么显然输出 $-1$。

在最开始设 $d=\frac{m}{n}$，那么 $n$ 每次要乘的数必定是 $d$ 的因数且必定是 $n$ 的因数。由于我们要次数最少，所以每次乘的要尽可能地多，又因为显然的每次最多也就只能乘上 $d$，所以就考虑每次 $n$ 乘上 $\gcd(d,n)$，最多只能乘上 $d$ 保证了这样子做的正确性，最后 $d$ 也要相应地除以 $\gcd(d,n)$。当 $\gcd(d,n)=1$ 时，退出循环。

如果退出循环后，$n$ 还不到 $m$，那就输出 $-1$，在代码里我是直接判 $d$ 是否大于 $1$，否则输出乘的次数。

不太理解为什么这题能评到绿。

CODE：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
ll n,m;
inline ll gcd(ll a,ll b)
{
	while(b^=a^=b^=a%=b);
	return a;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		if(m%n)
		{
			puts("-1");
			continue;
		}
		ll d=m/n,ans=0;
		while(1)
		{
			ll g=gcd(n,d);
			if(g==1) break;
			d/=g,n*=g,ans++;
		}
		if(d>1) puts("-1");
		else printf("%lld\n",ans);
	}
	return 0;
}