题解：P10869 [HBCPC2024] LCMs

题目传送门
题目简述

有一个数轴，数轴上的点都是大于 \(1\) 正整数。从一个点走到另一个点的代价是这两个点之间最小公倍数。题目要求计算从一个点走到另一个点的最小代价。
具体来说，对于给定的两个整数 \(x\) 和 \(y\) \((2 \leq a \leq b \leq 10^7)\)，需要计算从点 \(a\) 到点 \(b\) 的最小代价，这个代价是沿着数轴移动过程中所有相邻点之间代价的总和。
输入格式是多个测试用例，每个测试用例包含两个整数 \(x\) 和 \(y\)。输出格式是每个测试用例的最小代价。
样例中给出了几个测试用例的输入和输出，通过样例可以看出，计算最小代价的方法是找到从 \(a\) 到 \(b\) 的最短路径，使得路径上的所有相邻点之间的代价之和最小。由于题目中提到不允许走到 \(1\) 或更小的整数，所以起点和终点都至少是 \(2\)。
题目思路

首先我们分类讨论，求出几个特殊情况的答案：
先判断输入两点的大小，是否前小后大。如不是那么交换（交换与原问题等价）。

• 如果两点重合，即 \(x=y\)，那么长度为 \(0\)。
  
• 如果大点是小点的倍数，即 \(y \mid x\)，那么长度为 \(y\)。
  
• 如果两点不互质，即 \(\gcd(x,y) \neq 1\)，那么长度为 \(x+y\)（先到 \(\gcd(x,y)\) 再到 \(y\)）。
  

那两点不互质呢（\(\gcd(x,y)=1\)）？
我们只需要给 \({x,y,p_x,p_y,2}\)（\(p_i\) 是 \(i\) 的最小质因子）这 \(5\) 个点建一个团（全连图）求最短路就行了（不能到 \(1\) 只能到 \(2\)）。\(5\) 个点很少，可以用弗洛伊德。
时间复杂度：\(O(T \sqrt[2]{n})\) 卡在了找最小质因子的过程（用筛法可以优化到 \(O(T \log^2{n})\) 但没必要）。
代码

[code]#include#define 变量 long longusing namespace std;变量 n,距离[5][5];变量 计算距离(变量,变量);void 建图(变量,变量);变量 最小质因子(变量);int main(){        cin>>n;        for(变量 i=1,x,y;i>x>>y;                if(x>y)        swap(x,y);                if(x==y)        cout