题目描述
一张图有 \(n\) 个节点，编号为 \(1,2,3,\dots,n\)。其中 \(i\) 号节点会向 \(j\) 号节点连一条边权为 \(|i-j|\) 的无向边，当且仅当 \(\gcd(i,j)=i,\operatorname{lcm}(i,j)=j\) 时连边。现询问 \(q\) 次，每次询问求 \(x\) 到 \(y\) 的最短路径。
输入格式
第一行一个 \(T\)，表示数据组数。
每组数据的第一行两个正整数 \(n,q\)，表示节点数和询问次数。
接下来 \(q\) 行，每行两个正整数 \(x,y\)，表示起点和终点。
输出格式
对于每组询问，输出一个正整数。相邻两个输出以换行符隔开。
样例输入
1
6 4
1 4
3 5
2 5
2 4
样例输出
3
6
5
2
提示
对于 \(100\%\) 的数据，\(1\le T\le10^6\)，\(1\le n,q\le10^6\)，\(1\le x,y\le n\)，\(1\le \sum n,\sum q\le10^6\)。
请使用更快的 IO 方式。
先看时间复杂度，预测时间复杂度为 \(O(logn)\)，也就是说每组数据必须是 \(log\) 级别的时间复杂度
\(log\) 级别的算法就那几个，所以我们先看看题目的要求
很明显，每次询问不一定保证两个数肯定有一条边，那么便考虑是否有两条边的路可以走
这是肯定有的（\(x->1->y\)），而且这个中间点肯定为两个数的公因数（公倍数和公因数完全一样，但考虑到公倍数可能会超出限制，所以不考虑），那么便可以设一个 \(k\) ，且 \(k|x,k|y\)，又要满足 \(\min(x-k+y-k)\)
已经很明显了，\(k\) 就是两个数的最大公因数
时间复杂度也是 \(O(logy)\)
\(Code:\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
signed main()
{
int t,q;scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&q);
while(q--){
int ans=0;
int x,y;scanf("%lld%lld",&x,&y);
if(x>y) swap(x,y);
int gc=gcd(x,y);
ans=x-gc+y-gc;
printf("%lld\n",ans);
}
}
return 0;
}