官方题解

CashCollectFactory · 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 ，那么

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

上面两个式子可以看作长度为 (\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;
}