POJ 2739, POJ 2100

POJ 2566は，そのままだとしゃくとりできないが，累積和にしてソートするとしゃくとりできるようになる．なぜならば，問題が知りたいのは合計の絶対値であるから，累積和の差だけを考えればよいため．カンニング先→POJ-2566 : Bound Found - komiyamの日記

POJ 2739 Sum of Consecutive Prime Numbers

概要

与えられた整数値を連続した素数の和で表す方法は何通りあるか．

解法

素数列挙してしゃくとり．

vector<int> sieve_of_eratosthenes(ll n, vector<ll> &prime){
    vector<int> isPrime(n);
    for(ll i=2; i<n; ++i)
        isPrime[i] = i;
    for(ll i=2;i<n;++i)
        if(isPrime[i]){
            prime.push_back(i);
            for(ll j = i * i; j < n; j += i)
                isPrime[j] = 0;
        }
    return isPrime;
}

int main(){
    vector<ll> prime;
    sieve_of_eratosthenes(10010, prime);
    int n = prime.size();
    for(;;){
        int p;
        scanf("%d", &p);
        if(p == 0) return 0;
        int cnt = 0, sum = 0;
        for(int s=0,t=0;;){
            while(t < n && sum < p) sum += prime[t++];
            if(sum < p) break;
            if(sum == p) ++cnt;
            sum -= prime[s++];
        }
        printf("%d\n", cnt);
    }
}

POJ 2100 :Graveyard Design

与えられた整数値を，連続する二乗数の和で求めたい．

解法

何も考えずしゃくとり．

ll n;
vector<pair<ll, ll> > res;
int main(){
    scanf("%lld", &n);
    ll m = (ll)ceil(sqrt(n)) + 1;
    ll sum = 0LL;
    for(ll s = 1, t = 1;;){
        while(t <= m && sum < n){
            sum += t * t;
            ++t;
        }
        if(sum < n) break;
        if(sum == n){
            res.push_back(make_pair(s, t));
        }
        sum -= s * s;
        ++s;
    }
    printf("%d\n", res.size());
    EACH(i, res){
        printf("%lld ", i->second-i->first);
        for(ll j=i->first; j<i->second; ++j){
            printf("%lld%c", j, j + 1 == i->second?'\n':' ');
        }
    }
    return 0;
}