自动搬运

查看原文

来自洛谷，原作者为

	Naszt 数论，我的挚爱 | 看个人介绍请删除 "display: none;" 元素

搬运于2025-08-24 23:15:47，当前版本为作者最后更新于2025-03-06 20:44:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

距离

观前提醒

本题利用几何有更直观的做法，详见我用 desmos 画的。
不过为了严谨性，你可以结合着看下面的步骤。

思路分析

部分分

设 $x=\max\{a,b\},y=\min\{a,b\},x'=ky'$，
我们要最小化 $ans:=|x-x'|+|y-y'|$。
令 $y'=y$，有一个显然的上界 $ans\le\left\lfloor\frac{y}{2}\right\rfloor$。

若 $y$ 较小，我们可以枚举 $y'$：
确定了 $y'$ 的意义下，我们则要最小化 $|x-x'|$，
有：$k=\left\lfloor\frac{x}{y'}\right\rfloor \text{or} \left\lceil\frac{x}{y'}\right\rceil$。
再根据 $x'=ky'$ 即可算出 $x'$。

为了确保答案的正确性，我们可以枚举所有的：$|y-y'|<ans$
时间复杂度为 $\Theta(2ans)=O(y)$。

若 $\frac{x}{y}$ 较小，我们可以枚举 $k$：
确定了 $k$ 的意义下，我们则要最小化 $|y-y'|$，
有：$y'=\left\lfloor\frac{x}{k}\right\rfloor \text{or} \left\lceil\frac{x}{k}\right\rceil$。
再根据 $x'=ky'$ 即可算出 $x'$。

为了确保答案的正确性，我们可以枚举所有的：$|y-\frac{x}{k}|<ans$
时间复杂度为 $\Theta\left(\frac{x}{y-ans}-\frac{x}{y+ans}\right)=O\left(\frac{x}{y}\right)$。

合并做法

若 $y<\sqrt x$ 采用第一个方法，否则采用第二个做法。
这样的时间复杂度是 $O(\sqrt x)$ 的。
这何尝又不是一种分治。

但是这题的 $T$ 比较大，我们需要更好的复杂度分析。

时间复杂度

※ 这一部分内容可以没必要看，毕竟这是信息学（雾）。

我们以概率的方法分析 $ans$ 的值，
为了分析简单，我们只统计满足 $x'<x,y'<y$ 的 $(x',y')$。

确定了 $y'$ 的意义下我们定义 $X_{y'}=x\bmod y'$，
可以发现 $ans\le dis:=X_{y'}+|y-y'|$，
假设其是均匀且独立分布随机变量 $X_{y'}\in[0,y']\in\mathbb{Z}$，有：

$$\begin{aligned} &P(ans>v)\\ <&P(\min\{dis\}>v)\\ =&P\left(\min_{y'=1}^y\{X_{y'}+|y-y'|\}>v\right)\\ =&\prod_{y'=1}^yP(X_{y'}+y-y'>v)\\ =&\prod_{y'=y-v}^yP(y'-X_{y'}<y-v)\\ =&\prod_{y'=y-v}^y\frac{y-v}{y'}\\ =&\frac{(y-v)^v(y-v)!}{y!}\\ \approx&\frac{(y-v)^v\sqrt{2\pi(y-v)}(\frac{y-v}{e})^{y-v}}{\sqrt{2\pi y}(\frac{y}{e})^{y}}\\ \approx&e^{v}\left(\frac{y-v}{y}\right)^{y+0.5} \end{aligned} $$

※ 可能会有一定程度上的误差，这里无伤大雅。

可以发现我们时间复杂度最大时是 $y^2=x$ 时，
这时 $y$ 最大能取到 $10^8$，
但是 $P(ans>10^5)<10^{-50}$。

于是我们可以认为时间复杂度的上界为 $10^5$，足够通过本题的数据了。

当然，如果你想更精确的分析这个时间复杂度也可以，
我们设最坏概率为 $\epsilon$，这个解可以用朗伯 $W$ 函数表示，有：

$$v=y+(0.5+y)W\left(-\frac{y\sqrt[0.5+y]{e^{-y}ϵ}}{0.5+y}\right) $$$$v\approx y\left(1+W\left(-\frac{ϵ^{1/y}}{e}\right)\right) $$

更进一步的分析可以发现这个算法的时间复杂度是极快的，这里就不写了。

代码实现

工程细节

如果你真的把 $ans$ 取到 $\left\lfloor\frac{y}{2}\right\rfloor$ 来写代码，那下面的时间复杂度分析就没用了。

我们可以取 $ans$ 为当前的最优解，不断动态调整，先从 $y'=y$ 或 $k=\left\lfloor\frac{x}{y}\right\rfloor$ 开始遍历。

具体实现方法和更多细节可以看代码。

出题人代码

#include<bits/stdc++.h>
typedef long long i8;
i8 T,x,y;

i8 ydis(i8 ty){
  i8 kc=x/ty+1,xc=kc*ty,c=abs(ty-y)+abs(xc-x);
  i8 kf=x/ty  ,xf=kf*ty,f=abs(ty-y)+abs(xf-x);
  return std::min(c,f);
}i8 ysolve(){
  i8 ans=ydis(y);
  for(i8 t=1;t<ans;t++)
    ans=std::min(ans,ydis(y-t)),
    ans=std::min(ans,ydis(y+t));
  return ans;
}

i8 kdis(i8 k){
  i8 yc=x/k+1,xc=k*yc,c=abs(yc-y)+abs(xc-x);
  i8 yf=x/k  ,xf=k*yf,f=abs(yf-y)+abs(xf-x);
  return std::min(c,f);
}i8 ksolve(){
  i8 ans=kdis(x/y);
  for(i8 t=1;abs(1.0*x/(x/y-t)-y)<ans;t++)
    ans=std::min(ans,kdis(x/y-t));
  for(i8 t=1;abs(1.0*x/(x/y+t)-y)<ans;t++)
    ans=std::min(ans,kdis(x/y+t));
  return ans;
}

int main(){
  std::cin>>T;
  while(T--){std::cin>>x>>y;
    if(x<y)std::swap(x,y);
    std::cout<<(y<x/y?ysolve():ksolve())<<"\n";
  }return 0;
}

验题人代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;

ll x, y;

ll GetDistY(ll yy){
	ll ka = x / yy, xa = ka * yy;
	ll kb = x / yy + 1, xb = kb * yy;
	return min(abs(xa - x), abs(xb - x)) + abs(yy - y);
}

ll GetDistK(ll k){
	ll ya = x / k, xa = k * ya;
	ll yb = x / k + 1, xb = k * yb;
	return min(abs(xa - x) + abs(ya - y), abs(xb - x) + abs(yb - y));
}

ll Solve(){
	if(x < y) swap(x, y);
	if(x % y == 0) return 0;
	ll ans = 114514 + 1919810;
	if(y <= x / y){
		ans = GetDistY(y);
		for(ll i = 1; i < ans; ++i) ans = min(ans, min(GetDistY(y + i), GetDistY(y - i)));
	}
	else{
		ans = GetDistK(x / y);
		for(ll i = x / y + 1; y - 1.0L * x / i < ans; ++i) ans = min(ans, GetDistK(i));
		for(ll i = x / y - 1; 1.0L * x / i - y < ans; --i) ans = min(ans, GetDistK(i));
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T--){
		cin >> x >> y;
		cout << Solve() << endl;
	}
	return 0;
}