2013-04-09 08:01:05Morris
[UVA][math] 11254 - Consecutive Integers
Any positive integer can be written as the sum of several consecutive integers. For example,
| 15 | = | 1 + ... + 5 |
| = | 4 + ... + 6 | |
| = | 7 + ... + 8 | |
| = | 15 + ... + 15 |
Given a positive integer n, what are the consecutive positive integers with sum being n? If there are multiple solutions, which one consists of more numbers?
Input
Input consists of multiple problem instances. Each instance consists of a single positive integer n, where n ≤ 109. The input data is terminated by a line containing -1. There will be at most 1000 test cases.
Output
For each input integer n, print out the desired solution with the format:
N = A + ... + B
in a single line.
(Read sample output for a clearer representation of the exact formatting.)
Sample input
8
15
35
-1
15
35
-1
Sample output
8 = 8 + ... + 8
15 = 1 + ... + 5
35 = 2 + ... + 8
15 = 1 + ... + 5
35 = 2 + ... + 8
Problem setter: Cho
Source: Tsinghua-HKUST Programming Contest 2007
n = x + ... + y
(x+y)*(y-x+1) = 2*n = a*b
x+y = a
-x+y = b-1
x = (a-b+1)/2;
y = (a+b-1)/2;
#include <stdio.h>
int main() {
int n;
while(scanf("%d", &n) == 1 && n > 0) {
printf("%d = ", n);
n = n*2;
long long i, x, y, a, b;
long long rx = n/2, ry = n/2;
for(i = 2; i*i <= n; i++) {
if(n%i == 0) {
a = n/i, b = i;
if((a-b+1)&1)
continue;
if((a+b-1)&1)
continue;
x = (a-b+1)/2;
y = (a+b-1)/2;
if(y-x+1 > ry-rx+1)
rx = x, ry = y;
}
}
printf("%lld + ... + %lld\n", rx, ry);
}
return 0;
}
/*
n = x + ... + y
(x+y)*(y-x+1) = 2*n = a*b
x+y = a
-x+y = b-1
x = (a-b+1)/2;
y = (a+b-1)/2;
*/