Lucky Chains

题目链接

Educational Codeforces Round 139 (Rated for Div. 2)

D. Lucky Chains

取模的性质，更相减损术

思路：

我们假设链的长度为 w w w，不妨设 x ≥ y x\ge y x≥y，那么 g c d ( x + k , y + k ) = 1 ( 0 ≤ k ≤ w ) gcd(x+k,y+k)=1\quad (0\le k\le w) gcd(x+k,y+k)=1(0≤k≤w)。根据更相减损术，可以把式子写成如下形式： g c d ( x + k , y + k ) = g c d ( y + k , x − y ) = 1 gcd(x+k,y+k)=gcd(y+k,x-y)=1 gcd(x+k,y+k)=gcd(y+k,x−y)=1我们只要找到第一个不满足这个式子的 k k k 的取值，我们就知道了链的长度 w w w。

如果 g c d ( y + k , x − y ) ≠ 1 gcd(y+k,x-y)\not=1 gcd(y+k,x−y)=1，那么假设它们的最大公因数为 p p p，即 g c d ( y + k , x − y ) = p gcd(y+k,x-y)=p gcd(y+k,x−y)=p 的话， y + k , x − y y+k,x-y y+k,x−y 都应该是 p p p 的倍数， p p p 是它们的约数。因为 x − y x-y x−y 是个定值，所以我们可以枚举 x − y x-y x−y 的所有约数来得到 p p p。

不过枚举约数太慢了， n ∗ 1 0 7 ≈ 3 ∗ 1 0 9 n*\sqrt{10^7}\approx3*10^9 n∗107 ​≈3∗109，取模运算还很慢，八成会超时。考虑到我们上面其实并不需要知道 y + k , x − y y+k,x-y y+k,x−y 的最大公因数，我们只要他俩随便能有个相同的因数就行了，因此我们可以把这个最大公因数 p p p 拆成若干质因数，我们只对质因数进行验证就好了。

将某个数分解质因数可以用欧拉筛来预处理，每次标记合数的时候就记录一下这个合数由哪个质数算过来即可。之后查询会非常迅速（有几个质因数就只查几遍）。

而 y + k y+k y+k 是 p p p 的倍数就需要 k = ( y − y % p ) % p k=(y-y\%p)\%p k=(y−y%p)%p（ y y y 加上一个值得到最近的 p p p 的倍数）。 k k k 值就是所有约数中满足条件的最小的那个了。 0 ∼ k − 1 0\sim k-1 0∼k−1 都满足条件，链长就是 k k k 了。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e7+5;
const int inf=1e9;

int T,a,b,x;

bool vis[maxn];
int prime[maxn],lst[maxn],cnt;
void Eular(int n){
	vis[1]=true;
	lst[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			lst[i]=i;
		}
		for(int j=1,p=prime[1];j<=cnt && i*p<=n;p=prime[++j]){
			vis[i*p]=true;
			lst[i*p]=p;
			if(i%p==0)break;
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	Eular(1e7);
	cin>>T;
	while(T--){
		cin>>a>>b;
		if(a>b)swap(a,b);
		x=b-a;
		
		int ans=inf;
		for(int p=lst[x];p!=1;p=lst[x/=p])
			ans=min(ans,(p-b%p)%p);
		if(ans!=inf)cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}