X4C 题解

思路

$a + b \to a$ 差值为 $|a|$

$a + b \to b$ 差值为 $|b|$

…………

结论是后面会一直延续下去，都是 $|a|$ 或 $|b|$。

所以答案为 $\min(|a|,|b|,|a-b|)$

注：

再证明一件事情，如果 $a, b$ 异号，答案一定为 $0$ （样例2的提示）。

假设 $a \le 0 \le b$。

用伪代码那来解释一下:

while a+b > 0 : b = a + b

结束后

if a + b == 0 : {
    a = a + b  // a = 0
    b = a + b  // b = a
    abs(a - b) = 0
} else : {
    while a + b < 0 : a = a + b
    while a + b > 0 : b = a + b
    因为 a b 的差一直减小，
    所以显然最后 a + b = 0
}

重点细节

不开long long见祖宗

Code

#include <bits/stdc++.h>
#define int long long
#define endl() putchar('\n')
#define space() putchar(' ')
#define to_ans() putchar('&')
#define to_debug() putchar('^')
#define debug() puts("runs there")
using namespace std;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x * f;
}

void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	return void(putchar(x % 10 + 48));
}

int a, b;

signed main() {
	int T = read();
	while(T--) {
		a = read(), b = read();
		if(a * b <= 0) write(0), endl();
		else write(min({abs(a), abs(b), abs(a - b)})), endl();
	}
	return void(endl()), signed(0);
}

#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int a,b; cin>>a>>b; if(a<0&&b<0) cout<<min(abs(a),min(abs(b),abs(a-b)))<<"\n"; else if(a>0&&b>0) cout<<min(abs(a),min(abs(b),abs(a-b)))<<"\n"; else cout<<"0\n"; } return 0; }

考虑两种情况：

1. $a,b$ 符号相同：

   考虑经过操作后 $a,b,\lvert a-b \rvert$ 会变成什么。：

可以看出只进行零次或一次操作后可以取到最小值。

所以答案为 $\min(\lvert a \rvert,\lvert b \rvert,\lvert a-b \rvert)$。

2. $a,b$ 符号不同

   答案为 $0$。下面给出理由：

   因为改变 $a,b$ 的位置不会影响结果，所以设 $a$ 为正数，$b$ 为负数。

   注意到每次操作都会改变 $a$ 或 $b$ 的值，并且由于 $a$ 和 $b$ 异号，如果不断将绝对值较小的数加到绝对值较大的数上，就会不断减小两者的差值：

   • 假如 $\lvert a\rvert>\lvert b\rvert$，我们执行 $a\gets a+b$，$\lvert a\rvert$ 变小。
   • 假如 $\lvert b\rvert>\lvert a\rvert$，我们执行 $b\gets a+b$，$\lvert b\rvert$ 变小。

   由于每次操作都使得较大绝对值的数减小，因此可以类比辗转相减法，这种操作一定会在若干次后使得其中一个数变为 0。

代码：

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

int main(){
	int t;
	cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if((a<0&&b>0)||(a>0&&b<0)) cout<<0<<endl;
		else cout<<min({abs(a),abs(b),abs(a-b)})<<endl;
	}
	return 0;
}