题解：P10869 [HBCPC2024] LCMs

Vct14 · 2024-08-11 22:03:43 · 题解

题解代码没有分讨？我来交一发！

本场比赛最难的签到题。

题意：将整数 x 变为整数 y 代价为 \operatorname{lcm}(x,y)，求将 a 变为 b 的最小代价。注意：只能变为大于 1 的整数。

先讨论两种简单的情况。

如果 a=b，则最小代价为 0。不动即可。

否则如果 a\mid b，则一次变化最优，最小代价为 b，否则若变化多次，最后一步的代价一定大于或等于 b。

否则如果 \gcd(a,b)\ne1。

若走一步，代价 \operatorname{lcm}(a,b)。

否则因为 \operatorname{lcm}(x,y)\geqslant x，第一步的代价一定大于或等于 a，最后一步的代价一定大于或等于 b，理论最小代价 a+b，要实现这个代价只能走两步。设途经的数为 z，第一步走需使得 \operatorname{lcm}(a,z)=a，第二步走需使得 \operatorname{lcm}(z,b)=b。即 z 是 a,b 的公因数，可以走 a\to \gcd(a,b)\to b 实现。

设 \gcd(a,b)=d,a=dx,b=dy,(x,y)=1。则 a+b=d(x+y)，\operatorname{lcm}(a,b)=dxy。由于 a<b 且 a\nmid b，有 1<x<y,(x,y)=1，因此 (x-1)(y-1)>1，即 xy>x+y。所以 \operatorname{lcm}(a,b)>a+b。最小代价为 a+b。

只剩下 \gcd(a,b)=1 的情况。这种情况我们是走不到 \gcd(a,b) 的。

如果走一步，代价 \operatorname{lcm}(a,b)=ab。

如果走多步，因为互质的两数的最小公倍数是它们的乘积，为了使代价尽量小，我们可以选择途经 a 和 b 的最小质因子 \operatorname{minp}(a) 和 \operatorname{minp}(b) 使乘积尽量小。

若途经的数 z 与起点 a' 和终点 b' 都互质，代价为 a'z+b'z，我们可以选择途经 2 使得代价最小。

整理一下最终情况。设 p=\operatorname{minp}(a),q=\operatorname{minp}(b)。

以上代价取最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int lcm(int a,int b){
    return a/__gcd(a,b)*b;
}

int mnp(int a){
    for(int i=2; i*i<=a; i++) if(!(a%i)) return i;
    return a;
}

signed main(){
    int t;cin>>t;
    while(t--){
        int a,b;cin>>a>>b;
        if(a==b){
            cout<<0<<"\n";
            continue;
        }
        if(!(b%a)){
            cout<<b<<"\n";
            continue;
        } 
        if(__gcd(a,b)!=1){
            cout<<a+b<<"\n";
            continue;
        }
        int p=mnp(a),q=mnp(b);
        int a2=lcm(a,2),b2=lcm(2,b),p2=lcm(2,p),q2=lcm(2,q);
        cout<<min({a*b,a+p*b,a*q+b,a2+b2,a+p2+b2,a2+q2+b,a+p*q+qb,a+p2+q2+b})<<"\n";
    }
    return 0;
}

写晕了/yun，如果哪里有问题欢迎在评论区指出。