超高層ビル「みなとハルカス」[ICPC2018 国内予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1626

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/1626/review/3021282/hamayanhamayan/C++14

例として紹介されている15で考えてみる。
1+2+3+4+5 = (1+2+3+4+5) + 0*5
4+5+6 = (1+2+3)+3*3
7+8 = (1 + 2) + 6 * 2
15 = (1) + 14 * 1
どういう変形をしているか分からないかと思うが、n個の連続した整数の和は
(1+2+3+...+n) + x*n (0≦x)
の形で書けるということである。
そして、もう一つ大切なことが、nを固定するとBと上の式に基づいてxが一意に定まるということ。
　
nの上限を考えてみると、n*(n+1)/2+x*n=bなので、n=sqrt(b)が上限と分かる。
つまり、適当に見積もっても10^5くらい。
テストケースが10^3個なのを考えると、nで全探索しても問題なさそうである。
　
よって、各bについてnを全探索して、n*(n+1)/2+x*n=bを満たす整数xが存在するか確かめればいい。
存在すれば、そのうちの最大のnについて、最初がx+1で個数がn個の連続する整数の和が答えとなる。

void _main() {
    int B;
    while (cin >> B) {
        if (B == 0) return;

        int ans1 = B, ans2 = 1;
        rep(n, 2, 101010) {
            ll sm = 1LL * n * (n + 1) / 2;
            if (B < sm) break;

            int d = B - sm;
            if (d % n == 0) {
                ans1 = d / n + 1;
                ans2 = n;
            }
        }

        printf("%d %d\n", ans1, ans2);
    }
}