（1）优化计数背包

const int MAX_S = 1e6; // 最大可能的平方和
int main() {
    int n;
    cin >> n;
    vector<vector<bool>> dp(n+1, vector<bool>(MAX_S+1, false));
    dp[0][0] = true; // 初始状态：0个数组成0

    for(int i=1; i<=n; i++) {
        int l, r;
        cin >> l >> r;
        for(int k=l; k<=r; k++) { // 遍历所有可能的k值
            int square = k * k;
            for(int j=0; j<=MAX_S; j++) {
                if(j >= square && dp[i-1][j - square]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    int ans = 0;
    for(int j=0; j<=MAX_S; j++) {
        if(dp[n][j]) ans++;
    }
    cout << ans;
}
//
const int MAX_S = 1e6;
bitset<MAX_S+1> f[110]; // f[i]表示处理前i个数后的状态

int main() {
    int n;
    cin >> n;
    f[0][0] = 1; // 初始状态

    for(int i=1; i<=n; i++) {
        int l, r;
        cin >> l >> r;
        for(int k=l; k<=r; k++) {
            int shift = k * k;
            f[i] |= f[i-1] << shift; // 合并所有k值的可能性
        }
    }

    cout << f[n].count(); // 统计1的个数
}