G6009 [GESP202409 六级] 小杨和整数拆分 题解

知识点：完全背包、动态规划、完全平方数。

解题思路

先判断n是否一个平方，接着枚举是否能拆成两个平方。若都不是，去除所有因子4，结果模8为7则需4项，否则需3项。

为什么正确

平方检测排除1、2项；三平方定理指出且仅当n形如4^a(8b+7)时不能拆成三平方，四平方定理保证至多4项。

易错点

本参考解利用数论定理而非背包DP；平方根取整后须用乘法验证，1、2项必须优先判断。

复杂度

时间O(√n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int z=sqrt(n);
    if(z*z==n) {
        cout<<1;
        return 0;
    }
    for(int i=1;i*i<=n;i++) {
        int j=sqrt(n-i*i);
        if(j*j==n-i*i) {
            cout<<2;
            return 0;
        }
    }
    while(n%4==0)n/=4;
    cout<<(n%8==7?4:3);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。