【CodeForces - 1152C 】Neko does Maths（数学数论，lcm，gcd性质）

71 阅读 0 评论 47 点赞

我是靠谱客的博主精明蚂蚁，最近开发中收集的这篇文章主要介绍【CodeForces - 1152C 】Neko does Maths（数学数论，lcm，gcd性质），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题干：

给出a,b<=1e9，你要找到最小的k使得lcm(a+k,b+k)尽可能小，如果有多个k给出同样的最小公倍数，输出最小的一个k。

解题报告：

因为题目中k太多了，先化简一下公式，假设a>b ，则gcd(a+k,b+k) == gcd(a+k,a+b)；

下面给出一个简单证明：

z=gcd(a+k,b+k);

所以:(a+k)%z==0,(b+k)%z==0;

(a+k)%z==(b+k)%z;

a%z+k%z=b%z+k%z;

故 (a-b)%z=0;

还有个一般化的结论： gcd(a,a) = gcd(a,a) 　　　　 gcd(a,b) = gcd(a,a-b)(a>b)　　　　　　gcd(a,b) = gcd(b,a-b)(a>b)

所以公式可以化为：

lcm(a+k,b+k) = (a+k)*(b+k) / gcd(a+k,b+k). 要使得lcm(a+k,b+k)最小，则需要gcd(a+k,b+k)最大

因此只需要枚举(a-b)的因子将a+k凑至存在该因子fac（即a+k是fac的倍数），求出那个最小的k，（即k =（fac-a%fac）），取lcm最小值即可。

至于为什么k=fac-a%fac呢？下面给出简要证明：

这是因为首先k<fac，（因为假设k>=fac有上述条件成立，则总可以通过k-=fac的操作使得k变小且原式依旧成立），且k是在这个条件下是唯一的（这个很显然，不解释了），所以在模fac的意义下肯定有a+k==0(mod fac)，因此k=fac-a%fac，

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
ll a,b;
vector<ll> vv;
void solve(ll x) {//求出x的所有因子 
	for(ll i = 1; i*i<=x; i++) {
		if(x%i == 0) {
			vv.pb(i);
			if(i*i!=x) vv.pb(x/i);
		}
	}
}
ll lcm(ll a,ll b) {
	return a*b/__gcd(a,b);
}
int main()
{
	cin>>a>>b;
	if(a < b) swap(a,b);//保证a>b
	ll tmp = a-b,minn = lcm(a,b),ans=0;
	solve(tmp);
	int up = vv.size();
	for(int i = 0; i<up; i++) {
		ll k = vv[i] - a%vv[i];
		if(lcm(a+k,b+k) < minn) {
			minn = lcm(a+k,b+k);
			ans = k;
		}
	} 
	cout << ans << endl;
	return 0 ;
}