Graveyard Design POJ2100

投稿日：2022/12/24 更新日:2022/12/24

POJ

競プロ

問題：http://poj.org/problem?id=2100

問題

連続した正整数 $i, i+1, i+2, ...$ を考えます。その二乗の和 $i^2 + (i+1)^2 + ...$ が $n$ と一致する数列をすべて列挙してください。

解法

尺取り法をつかう。

区間 $[l, r)$ の二乗の和が $n$ 未満であれば、 $r$ を増やし、そうでなければ $l$ を増やす。総和は適宜更新していき、 $n$ と一致した範囲を記録しておく。

二乗の和を求めているので、 $l, r$ は最大でも、 $\sqrt{n}$ までを考えれば良い。

実装

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

void solve(){
    long long n;
    cin >> n;
    long long l = 1, r = 1;
    long long sum = 0;
    vector<pair<long long, long long>> ans;
    while(l*l <= n){
        if(sum == n){
            ans.push_back(make_pair(l ,r));
        }
        if(r*r <= n && sum < n){
            sum += r*r;
            r++;
        }else{
            sum -= l*l;
            l++;
        }
    }

    cout << ans.size() << '\n';
    for(int i = 0;i < ans.size(); ++i){
        cout << ans[i].second - ans[i].first;
        for(int k = ans[i].first;k < ans[i].second; ++k){
            cout << " " << k;
        }
        cout << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
    return 0;
}