题目描述
给定一个数 \(X\), 求最少加减多少个平方数可以得到 \(X\)
输入
\(t\) 个样例, 每行一个数 \(X\)
\(t = 100\), \(X = 10 ^{11}\)
输出s
\(n\) 表示最少需要几个数, 然后跟着 \(n\) 个数, 表示加减哪些数的平方数
分析
首先我们考虑 \(n=1\) 的情况, 即 \(X\) 是完全平方数, 那我们判断 sqrt(X) * sqrt(X) 是否等于 \(X\) 即可
然后我们就很自然能想到平方差, 即考虑X是否能用 \(A^2-B^2\) 表示呢?
我们知道如果可以, 就会有 \(X=A^2-B^2=(A+B)(A-B)\) , 而 \((A+B)\) 和 \((A-B)\) 的差为2B, 是个偶数, 所以 \((A+B)\) 和 \((A-B)\) 是同奇偶性的, 换句话说, 如果一个数可以分解成两个同奇偶性的数的乘积, 那么它就可以用平方差来表示
那么什么样的数可以分解成两个同奇偶性的数的乘积呢?
当X为奇数的时候, 我们知道任何奇数都可以分解成两个奇数的乘积, 最简单的就是1乘以它自己, 所以所有奇数都可以用平方差表示, 排除那些完全平方数即可
当X为偶数的时候呢, 这里引入一个知识点: 偶数可以分成两类, 一类是4的倍数, 即 \(4k\), 另一类是 \(4k-2\). \(4k-2=2(k-1)\), 即奇数和2的乘积, 无论怎么分解, 2也会在其中一个因数中, 那个因数是偶数, 另一个就是奇数, 所以 \(4k-2\) 类型的偶数肯定不能分解成两个奇偶性相同的因数, 也就不能用平方差表示; 而 \(4k\) 类型的偶数, 肯定可以分出一个4出来, 而4又是\(2\times2\), 这样 \(4k\) 就是 \(2\times2k\), 因数肯定是两个偶数, 所以 \(4k\) 类型, 也即是4的倍数的偶数可以表示为 \(A^2-B^2\)
平方差考虑了, 我们还要考虑平方和的情况, 会不会 \(X=A^2+B^2\) 呢? 我们只需要枚举A, 看看有没有合法的B满足这个式子即可, 这一步时间复杂度是 \(O(\sqrt{X})\)
如果上述情况都不满足, 也即是 \(X\) 即不是奇数, 也不是4的倍数, 也不能用平方和来表示, 那此时 \(X\) 一定是偶数, 让 \(X\pm1^2\) 就可以得到一个奇数, 然后就可以用平方差表示
综上, 完全平方数是1步操作, 满足平方差或平方和是2步操作, 剩下均是3步操作