自动搬运

查看原文

来自洛谷，原作者为

	CashCollectFactory 这个家伙不懒，但什么都留下了

搬运于2025-08-24 22:52:24，当前版本为作者最后更新于2023-12-03 12:13:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这一套 ICPC 的问题全是关于原神的诶，重云不可爱，但还是必须交一份题解来宠爱重云呢~

题目大意

给出两个正整数 $a,b$，每次可以进行三种操作：都加一，都减一和都除以一个它们共同的质数因子，判断最少多少次能使得其中一个数为 $1$。

题目分析

一眼看上去就是深度优先搜索吧？

总的来说，如果不进行除法操作，那么 $a$ 与 $b$ 的差值是固定的，如果存在一个数能够整除 $a$ 和 $b$，那么一定也能整除它们的差值，那么就可以将其差值进行质因子分解，将 $a$ 和 $b$ 中的较小数加或减到距离质因子最小的数，对 $a$，$b$ 及差值同时除质因子，以此反复即可，当无质因子时就只能一直减了。

如果只使用前两种操作，那么 $\delta = a - b$ 的值是不变的，而且 $a$ 和 $b$ 的公共质因数一定也是 $\delta$ 的质因数。而且当我们想除以一个质因数 $g$ 时，我们一定会先通过前两种操作来到最近的 $g|a$ 且 $g|b$ 的状态然后直接除 $g$ （先加减 $k$ ，再除 $g$ ，再加减 $1$ 肯定优于加减 $2k$ ）。

因此记 $f(a, \delta)$ 表示从 $(a, a + \delta)$ 得到 $1$ 的步数，枚举 $\delta$ 的质因数 $g$ ， $f(a, \delta)$ 可以由 $f(\lfloor\frac{a}{g}\rfloor, \frac{\delta}{g})$ 和 $f(\lceil\frac{a}{g}\rceil, \frac{\delta}{g})$ 转移得到。因此状态的第二维只有 $\delta$ 的因数个。

但状态的第一维如果和除以因数的顺序有关，那状态数又超了。但无需担心，实际上对于整数 $x$ 和 $a_1, a_2, \cdots, a_k$ ，$x$ 以任意顺序被 $a_i$ 进行整数除法（无论上取整或下取整），结果至多只有两种。因此总的状态数仍然是因数级别的。

通过以下方式完成证明：

若 $x$ 以任意顺序被 $a_i$ 进行下取整的整除得到的结果是 $k_1$ ，进行上取整的整除得到的结果是 $k_2$ ，那么

$k_1\prod\limits_{i=1}^n a_i \le x \le (k_1 + 1)\prod\limits_{i=1}^n a_i - 1$

$(k_2 - 1)\prod\limits_{i=1}^n a_i + 1 \le x \le k_2\prod\limits_{i=1}^n a_i$

该式可通过数学归纳法证明。

上面两个式子可以看作长度为 $(\prod\limits_{i=1}^n a_i - 1)$ 的两个区间，显然只有当 $k_2 + 1 = k_1$ 或 $k_2 = k_1$ 时两个区间才有交集。

由于以任意顺序进行全部上取整的整除得到的结果一定是最大的，进行全部下取整的整除得到的结果一定是最小的，那么上下整除混合得到的结果自然在两者中间。该性质得证。

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,a,b,t;
vector<int>v;
unordered_map<int,int>level;
int gethash(int b,int c) {//哈希
    return b*1e9+c;
}
int DFS(int b,int c) {
    if(b==1)return 0;
    if(c==1)return b-1;//差值为1，只能一直减
    if(level[gethash(b,c)])return level[gethash(b,c)];//记忆化搜索
    int mn=b-1;//至少需要的次数
    for(auto i:v)//遍历所有的质因子
        if(c%i==0) {//如果还没有除过
            int ans=b%i;//获得差距
            mn=min({mn,ans+1+DFS(b/i,c/i),i-ans+1+DFS(b/i+1,c/i)});
            //分别是b大于i的情况和b小于i的情况，+1是因为进行了一次除
        }
    return level[gethash(b,c)]=mn;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>a>>b;
        if(a<b)swap(a,b);//强制b为小值
        int c=a-b;
        v.clear();
        for(int i=2; i<=c/i; i++)
            if(c%i==0) {//获得质因子
                v.push_back(i);
                while(c%i==0)c/=i;
            }
        if(c>1)v.push_back(c);//最后除剩的也是质因子
        cout <<DFS(b,a-b)<<endl;//记忆化搜索
    }
    return 0;
}