题解：AT_arc150_b [ARC150B] Make Divisible

cmrhhh · 2024-07-27 08:33:51 · 题解

[ARC150B] Make Divisible解题报告

前言

这题非常好，窝被根号分治骗进来，写了数论分块而去，感觉题解区大家思路多少都有点不同。我写的数论题很少，看不懂大佬的过程，只能手推了，下面是蒟蒻的过程。

思路

先看 b\le a 时，把 b 补齐 a 即可，之后默认 b>a 虽然没啥用。

然后自然有柿子 k(A+X)=(B+Y)，其中 X,Y\ge 0 且 k\in \mathbb{Z^+}。

然后很自然就是用 X,Y>0 推出 k 的范围，试一下发现很好解出：

然后感性理解一波，B+Y=\left\lceil\frac{B}{A+X}\right\rceil\times(A+X)。

因为此时 (A+X)\mid(B+Y)。

那么完整柿子：

发现向上取整可以整数分块，怎么搞？感性理解下面柿子：

分块时某一段的左端点一定是一段里面最优的。

代码

在实现上出了点锅，在 r 取到最后的时候还要再算一次。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int t;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--){
        ll a,b;
        cin>>a>>b;
        if(a>=b){cout<<a-b<<"\n";continue;}//b不足就补齐
        ll ans=1e18,r;
        for(ll l=a;l<=b-1;l=r+1){
            r=min(b-1,(b-1)/((b-1)/l));
            ans=min(ans,(l-a)+(1+(b-1)/l)*l-b);
        }r++;
        ans=min(ans,(r-a)+(1+(b-1)/r)*r-b);
        cout<<ans<<"\n";
    }
    return 0;
}