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;
}