Codeforces Round #554 (Div. 2) C. Neko does Maths（数学+GCD）

传送门

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题意：

　　给出两个整数a,b；

　　求解使得LCM(a+k,b+k)最小的k，如果有多个k使得LCM()最小，输出最小的k；

思路：

　　刚开始推了好半天公式，一顿xjb乱操作；

　　后来，看了一下题解，看到一个引理：

　　GCD(a,b) = GCD(a,b-a) = GCD(b,b-a)(b > a)

　　

假设GCD(a,b) = c;
a%c = 0;
b%c = 0;
那么(b-a)%c = 0;
这证明了a和(b-a),b和(b-a)有公约数c;
假设GCD(a,b-a)=c' > c;
那么，a%c' = 0;
(b-a)%c' = 0;
(b-a)%c' = b%c'-a%c';
所以 b%c' = 0;
那么GCD(a,b) = c' > c，与假设矛盾；
GCD(b,b-a)同理；
故命题得证；

简单证明

　　有了这个引理后，解题思路变得异常清晰；

　　首先将LCM(a+k,b+k)转化一下：(a < b)

　　

　　

　　情况①，遍历，不会遍历太多次的；

　　情况②，公式；

　　情况③，枚举b-a的约数；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define ll long long
 6 
 7 ll a,b;
 8 
 9 ll GCD(ll a,ll b)
10 {
11     return a == 0 ? b:GCD(b%a,a);
12 }
13 ll LCM(ll a,ll b)
14 {
15     return a/GCD(a,b)*b;
16 }
17 ll F(ll k)
18 {
19     return (a+k)*(b+k)/GCD(a+k,b+k);
20 }
21 bool isSat(int i,ll k)//判断k是否可以更新为i-a
22 {
23     ll curK=i-a;
24     if(curK < 0 || F(curK) != LCM(a+curK,b+curK))
25         return false;
26     if(F(curK) < F(k) || F(curK) == F(k) && curK < k)
27         return true;
28     return false;
29 }
30 ll Solve()
31 {
32     if(a > b)
33         swap(a,b);
34     int d=b-a;
35     if(d == 0)
36         return 0;
37 
38     ll k=1;
39     for(;GCD(d,a+k) != 1;k++);///情况①
40     for(int i=1;i*i <= d;++i)///情况③
41     {
42         if(d%i != 0)
43             continue;
44         if(isSat(i,k))///a+k=i
45             k=i-a;
46         if(isSat(d/i,k))///a+k=d/i
47             k=d/i-a;
48     }
49     ///情况②，GCD()为定值，k越小LCM()就越小
50     ll x=(a/d+(a%d == 0 ? 0:1))*d;///a+k=k*d(k*d:>=a的最小的d的倍数)
51     if(isSat(x,k))
52         k=x-a;
53 
54     return k;
55 }
56 int main()
57 {
58     scanf("%lld%lld",&a,&b);
59     printf("%lld\n",Solve());
60 
61     return 0;
62 }

View Code

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄