投資錢景>買台積電就對了金豪禮★拿現金最實在!法人:14檔今年本業虧定了買太多也不行!7500...
2013-04-09 08:01:05 人氣(26) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][math] 11254 - Consecutive Integers

0
收藏
0
推薦

Problem B - 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

Sample output
8 = 8 + ... + 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;
*/

11254Consecutive Integers
台長:Morris
人氣(26) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][窮舉+組合] 10574 - Counting Rectangles
此分類上一篇:[UVA] 10264 - The Most Potent Corner

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文