UVa 11254 Problem B - Consecutive Integers
Problem B - Consecutive Integers
http://uva.onlinejudge.org/external/112/11254.html
問題概要
ある整数を連続する正の整数の和で表せ。
n ≤ 1000000000
解法
約数を見る。
約数が奇数kの場合、対になるもう一つの約数を中心とした連続したk個の正の整数の和で表すことができる。
つまり、6は2を中心とした3個の整数の和、つまり1, 2, 3で表すことが可能。
ただし、注意すべきは5の場合などの整数の和の開始位置が負になる場合。
すなわち、5*1 = 5のことから、1を中心とした5個の整数、
-1 0 1 2 3
であらわすことができる。
しかし、始点が負である。問題は正の整数の和で表さなければない。
この場合、1と-1は打ち消し合う。
0は消しても和に影響しない。
よって,
2 3
となるのである。
ソース
#include<iostream> #include<vector> #include<cstdio> #include<cmath> #include<algorithm> #define REP(i,b,n) for(int i=b;i<(int)n;i++) using namespace std; int head, tail, maxLen; void solve(int mid, int tmpLen){ if(tmpLen%2 == 0)return; int mini = mid - tmpLen/2, maxi = mid+tmpLen/2; if(mini <= 0){ tmpLen += mini * 2; tmpLen--; } if(tmpLen > maxLen){ head = max(mini, mini * -1 + 1); tail = maxi; maxLen = tmpLen; } } int main(){ int n; while(1){ maxLen = -1; scanf("%d", &n); if(n < 0)break; REP(i, 1, sqrt(n)+1){ if(n %i == 0){ solve(n/i, i); solve(i, n/i); } } printf("%d = %d + ... + %d\n", n, head, tail); } return 0; }