场外选手口胡
题目传送门
题目大意：
\(T\) 组询问，每次给定两个正整数 \(a, b\)。
定义一种操作为：选择一个正整数 \(y\)，将 \(x\) 变成 \(x\times \gcd(a, y)\)。
对每组询问回答：将 \(a\) 变成 \(y\) 最少需要几次操作。
数据范围：\(1\le T\le 2\times 10^5,1\le a\le b\le 10^{18}\)。
思路：
读完题确定思考方向应该是选择一种策略使得每次 \(a\) 的增长尽量大，考虑贪心。
考虑到 \(\gcd(a, y)\) 是整数，所以首先判掉一种无解情况：当 \(a\nmid b\) 时，必定无解。
接着令 \(c = \frac{a}{b}\)。
因为操作中的 \(y\) 是自己指定的，所以 \(a\) 每次扩大的倍数和它自己的质因子及其指数相关，我们想让它扩大的幅度尽量大，就得每次尽量选择它和 \(c\) 的质因子重合的尽量多的质因子，即 \(\gcd(a, c)\)。
通俗来讲就是每次尽量增大一点，多囊括一点质因数，在更靠近目标的过程中顺便拥有更多的选择权。
所以做法就是每次求出 \(d = \gcd(a, c)\)，然后 \(a\leftarrow a \times d\)，\(c\leftarrow\frac{c}{d}\)，直到 \(a = b\)。
在此过程中还要判断 \(d\) 是否为 \(1\)，若 \(d = 1\) 且 \(a \ne b\)，那么就不可能成功了，因为此时 \(c\) 中存在被垄断的质因子。
以上都为感性理解，接下来开始严谨（可能不那么严谨）证明。
这里从决策包容性来证明。
从质因数分解的方向来思考。
在操作进行的任意时刻，设
\[a = p_{1}^{\alpha_1}\times p_{2}^{\alpha_2}\times\cdots\times p_{k}^{\alpha_k} \]设 \(d = \gcd(a, c)\)，是最优策略 \(y\) 所产生的贡献，\(d'\) 为选择另外一个 \(y'\) 带来的贡献，且 \(d'< d\)。
设
\[d = p_{1}^{a_1}p_{2}^{a_2}\cdots p_{k}^{a_k} \]\[d' = p_{1}^{b_1}p_{2}^{b_2}\cdots p_{k}^{b_k} \]因为 \(d' < d\)，所以 \(\forall i\in[1, k],b_i\le a_i\)，并且 \(\exists i\in[1, k],b_i < a_i\).
按两种方式将 \(a\) 操作之后分别得到：
\[a = p_{1}^{\alpha_1 + a_1}\times p_{2}^{\alpha_2 + a_2}\times\cdots\times p_{k}^{\alpha_k + a_k} \]\[a' = p_{1}^{\alpha_1 + b_1}\times p_{2}^{\alpha_2 + b_2}\times\cdots\times p_{k}^{\alpha_k + b_k} \]所以 \(\exists i\in[1, k], \alpha_i + b_i < \alpha_i + a_i\).
接着考虑这一次操作对下一次操作的影响。
设从 \(a\) 中取出来若干质因数组成的集合 \(S = \{n_1\cdot p_1, n_2\cdot p_2\cdots n_k\cdot p_k\}\)，是由 \(n_1\) 个 \(p_1\)，\(n_2\) 个 \(p_2,\cdots,n_k\) 个 \(p_k\) 组成的多重集，其中 \(\forall i\in [1, k], 0\le n_i\le \alpha_i + a_i\)。
同理可设从 \(a'\) 中取出来若干质因数组成的集合 \(S' = \{n'_1\cdot p_1, n'_2\cdot p_2\cdots n'_k\cdot p_k\}\)，是由 \(n'_1\) 个 \(p_1\)，\(n'_2\) 个 \(p_2,\cdots,n'_k\) 个 \(p_k\) 组成的多重集，其中 \(\forall i\in [1, k], 0\le n'_i\le \alpha_i + b_i\)。
定义 \(t\) 为下一次操作选择 \(y\in \mathbb{N}\) 可产生的贡献，从 \(S\) 中选择产生的所有 \(t\) 值组成不可重集合 \(S_1\)，从 \(S'\) 中选择产生的所有 \(t\) 值组成不可重集合为 \(S_2\)。
由于 \(\exists i\in[1, k], \alpha_i + b_i < \alpha_i + a_i\)，所以容易得出 \(S_2\subsetneqq S_1\)。
所以选择乘上 \(d'\) 后未来能做到的，选择乘上 \(d\) 后未来也能达到，即 \(d\) 的的适用性更广。
因此在任意局面下，做出局部最优解后，这个局部最优策略提供的可能性包含其他所有的策略提供的可能性，此贪心策略是正确的。
证毕。
同时，再此贪心策略下，每次 \(a\) 至少要乘二，所以时间复杂度为 \(O(T\log b)\)。
\(\texttt{Code:}\)
#include <iostream>
using namespace std;
typedef long long ll;
int T;
ll a, b;
ll gcd(ll a, ll b) {
if(!b) return a;
return gcd(b, a % b);
}
void solve() {
scanf("%lld%lld", &a, &b);
if(b % a != 0) {
puts("-1");
return ;
}
ll c = b / a;
if(c % a != 0) {
puts("-1");
return ;
}
int res = 0;
while(a != b) {
ll d = gcd(a, c);
a *= d, c /= d;
++res;
}
printf("%d\n", res);
}
int main() {
scanf("%d", &T);
while(T--) {
solve();
}
return 0;
}