GCD

GCD 洛谷

题目描述

一张图有 \(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;
}