题解：P11130 【MX-X5-T2】「GFOI Round 1」Interstellar

what_can_I_do · 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;
}