杭电多校赛第8场 1010 Rikka with Square Numbers

沙野博士 / 2023-08-18 / 原文

题意

给两个数字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;
}