浅谈YBH算法1——YBH规律

大家好，欢迎来到IT知识分享网。

ybh 本人
在算法世界中，有许多算法由YBH命名。这些算法是由我国算法家杨秉涵（2007——）发明的，主要包括YBH规律、YBH网络流、YBHdp，以及数据结构YBHTree、YBHST表等。今天先介绍最简单的YBH规律。
YBH规律是一种十分玄学的算法，它可以在最多线性的时间复杂度中解决一些难题，被OIer戏称为“蒟蒻的快乐，大佬的眼泪”。
先从一道经典的YBH规律例题入手
CF1543A Exciting Bets
题目大意：
给你两个非负整数a,b ，你可以对它们做如下操作：

1. 两个数同时加1
2. 两个数同时减1，前提是两个数都是正数

注意：$gcd(x,0)=x$。经过一番操作，问能够构成的最大的 $gcd(a,b)$ 为多少？若该值可以达到无限，那么输出两个0，否则输出最大的 $gcd(a,b)$ 以及操作步数。
看起来，这道题很难，但实际上，这道题通过YBH规律算法能够轻松求解。先来观察样例数据。

4 8 5 1 2 4 4 3 9 

其中第一行之后的每一行为一组数据，分别为a和b。再来看看它们对应的输出

3 1 1 0 0 0 6 3 

看到第三组数据，输出了0，说明 $gcd(a,b)$ 可以无限。而4和4相等，看到这里，大家应该都知道了，只要两个数相等，结果就是无限。
继续观察第1、2、4组数据。发现这个最大的 $gcd(a,b)$ 其实就是a与b差值的绝对值。下面让我们来解释：（不想看的可以自动跳过）

假设我们将a和b直接减到0和b-a（假设$a<b$，当然可以调换），那么此时，$gcd(a,b)=b-a$，然而在a与b固定差值的情况下（同时加减差值不变），$gcd(a,b)$ 不可能比 $b-a$ 更大了（有兴趣的读者可以自己试验），因此

$gcd(a+x,b+x),(a\ne b,x\ge min(-a,-b)$且为整数$)$

的最大值为 $b-a$。

那操作步数怎么算呢？
首先，要么一直加，要么一直减，不可能又加又减。那么什么时候 $gcd(a,b)=b-a$ 呢？很明显，只有三种情况：

1. $ab=0$
2. $\frac{a}{b}=b-a$
3. $\frac{b}{a}=b-a$

意思就是说，a和b都是 $b-a$ 的倍数。那么我们只需要选择离原来的a,b近的 $b-a$ 的倍数来计算步数即可。单组数据的时间复杂度为$O(1)$。代码如下：

#include<bits/stdc++.h> using namespace std; int main() { 
    int n; scanf("%d",&n); while(n--) { 
    int a,b; scanf("%d%d",&a,&b); if(a>b) swap(a,b); if(a==b) printf("0 0\n"); else printf("%d %d\n",b-a,min(b%(b-a),b-a-b%(b-a))); } return 0; } 

（注：原OJ提交需要开long long，否则会溢出）

总结一下，YBH规律的核心思想是把一道题分成三步来做：

1. 猜想结果
2. 证明猜想
3. 代码实现

正如杨秉涵在初中的信息学老师何异所言，做一道找规律的题目，需要“大胆猜想，小心求证”。