ARC150B

数论分块

Make Divisible

题目链接:https://atcoder.jp/contests/arc150/tasks/arc150_b

题意:给出A,B求出X,Y,满足$(A+X)|(B+Y)$,且最小化$X+Y$,其中$A,B \in (1,1e9)$

分析:设比值$k=(B+Y)/(A+X)$,则有

$$Y=kX+kA-B,Y>=0 \\ ans=X+Y=(k+1)X+kA-B$$

则可以得到X的限制

$$X>=B/k-A$$

一个更好的形式

$$x>=\lfloor(B-1)/k\rfloor-A+1$$

这样,我们可以枚举k来计算答案.

由数论分块可知,最多有$\sqrt B$个有效的k.于是不断地跳k,就可以在复杂度为根号的时间内解决问题.

ll k=1,ans=A+B;
while(k<B){
    ll x=max(0ll,(B-1)/k-A+1);
    ans=min(ans,(k+1)*x+k*A-B);
    ll r=(B-1)/((B-1)/k);
    k=r+1;
}