题意
给两个数字a，b 每次操作可以给a加上或者减去一个平方数，问需要最少几次操作使a变成b
\(1 <= a , b <= 1e9 , a \neq b\)
解
找规律。
将问题转化成怎么用平方数凑成\(abs(a - b)\) ， 用k表示这个数字。
如果k是一个平方数，那么一步就可以搞定。
由于相邻两个平方数相减可以得到所有的奇数，所以奇数需要2步搞定。
而偶数，由于偶数加1、减1为奇数，所以偶数最多需要3步搞定。
偶数当中也有一些可以两步搞定的，比如\(12 = 16 - 4 = 4^2 - 2^2\)
又发现如果是4的倍数，也可以只用2步完成，因为\((n+1)^2 - (n-1)^2 = 4n\)
现在还剩下\(k \% 4 == 2\)的情况，如果k可以被表示为两个平方数的和或者差的话就是2步，否则就是3步。
表示成和的话就枚举\(k\)以内的所有平方数即可。
而表示成差的话，令\(k = (p - q)(p + q)\)，因为\(k \% 4 == 2\) ,所以\(k = 4n+2\) , \(k / 2 = 2n+1\)也就是说k里面只有1个质因数2。所以\(p - q , p+q\)必然是一奇一偶，所以k无法表示成平方数的差。
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int T , a , b , c , t , flag;
cin >> T;
while(T--)
{
cin >> a >> b;
c = a - b;
c = c > 0 ? c : -c;
t = sqrt(c);
if(t * t == c)
cout << 1 << '\n';
else
{
if(c & 1)
cout << 2 << '\n';
else
if(c % 4 == 0)
cout << 2 << '\n';
else
{
flag = 0;
for(int i = 1 ; 1ll * i * i <= c ; ++i)
{
t = sqrt(c - i * i);
if(1ll * t * t + 1ll * i * i == c)
{
flag = 1;
// cout << i << ' ' << t << '\n';
break;
}
}
cout << 3 - flag << '\n';
}
}
}
return 0;
}