P11130 解题报告

· · 题解

更好的阅读体验

场外选手口胡

题目传送门

题目大意：

定义一种操作为：选择一个正整数 $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;
}