# [题解] 2023 杭电多校 Rikka with Square Numbers [数论]

哎，数学！

# 题目大意

每次操作可以加或者减一个完全平方数，问至少多少次可以把$a$ 变成$b$。
$1 \le a,b\le 10^9$。

# 题解

看到这个题面首先想了$dp$ 或者搜索的做法。
发现这里的加减两个方向的转移其实没办法很好地$dp$。而且并没有找到合理的操作策略，不像是直接能递推出来的。
所以大概率是个结论题。然而我对数学不那么敏感，也推不出来什么式子。
如果当初先暴力打个表说不定就有思路了，那就能看到答案其实只有$1$ 或$2$ 或$3$。
那么我们就分类讨论。为了方便这里不妨令$a\gt b$，反正操作可逆，做等价交换。

• 答案是$1$ 的情况：即$a-b$ 是一个完全平方数。
• 答案是$2$ 的情况：$a-b$ 不是完全平方数，但是可以由两个完全平方数或加或减凑出来。令$d=a-b$：
  • 如果是两个平方数相加得到$d$，令$d=x^2+y^2$，这时候通过枚举即可在$\mathcal{O}(\sqrt d)$ 时间内判断。
  • 如果是两个平方数相减得到$d$，令$d=x^2-y^2$，不妨令$x\gt y$。我们有平方差公式$d=x^2-y^2=(x+y)(x-y)$。这时再对$x$ 和$y$ 的奇偶性做一下讨论：
    • $x$ 和$y$ 一奇一偶，那么$(x+y)(x-y)$ 显然是奇数。一个奇数$d$ 必然可以找到$x$ 和$y$ 满足$d=x+y$ 且$x-y=1$。也就是说 d 为奇数的情况自然满足操作两步可达。
    • $x$ 和$y$ 双奇或双偶，那么$(x+y)(x-y)$ 显然是$4$ 的倍数。令$d=4k$，这时令$x=k+1,y=k-1$ 即可满足。
• 答案不为$1$ 或$2$ 时，注意到这时$d$ 一定为偶数 ($d$ 为奇数一定至少$2$ 步可以完成), 那么我们只要先用$1$ 步将$d$ 减掉$1$, 即可再用$2$ 步满足，所以答案为$3$。
  至此，所有情况讨论完了。代码主要只有一个判断两平方之和的循环，时间复杂度$\mathcal{O}(\sqrt{a+b})$。

# 代码

#include<cstdio>

#include<map>

#include<cmath>

const int MAXN=1e9;

bool isqr(const int &x){

	if(x==0) return 0;

	int t=sqrt(x);

	return t*t==x;

}

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int a,b;

		scanf("%d%d",&a,&b);

		int d=a-b;

		if(d<0) d=-d;

		if(d==0)

			printf("0\n");

		else if(isqr(d))

			printf("1\n");

		else if(d&1 || d%4==0)

			printf("2\n");

		else{

			bool fg=0;

			for(int i=1;i*i<d && !fg;++i)

				if(isqr(d-i*i))

					fg=1;

			if(fg)

				printf("2\n");

			else

				printf("3\n");

		}

	}

}