川添さん問題03 ステップ・アップ・サム

■■■問題■■■

自然数nを、2つ以上の連続する自然数の和で表すことを考えましょう。

例えば、18は 5 + 6 + 7 や 3 + 4 + 5 + 6 と表すことができます。
同様に、15は 7 + 8 や 4 + 5 + 6 や 1 + 2 + 3 + 4 + 5 と表すことができます。
いずれもこれら以外の表し方は存在しません。

この表し方における最も小さな数 (上で赤字で記した数のことです) を、
全ての表し方について和をとったものを F(n) と定義します。

例えば F(18) = 5 + 3 = 8、F(15) = 7 + 4 + 1 = 12 です。
同様に、F(105) = 139、F(256) = 0、F(945) = 1698 であることが確かめられます。

標準入力から、自然数 n (1 <= n <= 100億) が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input2";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("18");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("15");
            //12
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("105");
            //139
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("256");
            //0
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("945");
            //1698
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

        long Answer = 0;

        //項数でループ
        for (long Kousuu = 2; ; Kousuu++) {
            //1から始めたとしても、オーバーならBreak
            long wkSum = (Kousuu * (Kousuu + 1)) / 2;
            if (wkSum > N) break;

            long Syokou;
            if (ExecNibunhou(N, Kousuu, out Syokou)) {
                Answer += Syokou;
            }
        }
        Console.WriteLine(Answer);
    }

    //S = 項数 * (初項+初項+項数-1) /2
    //は、初項に対して単調増加なので、初項を2分法で探す
    static bool ExecNibunhou(long pN, long pKousuu, out long pSyokou)
    {
        pSyokou = -1;
        long L = 1;
        long R = pN / 2; //最低項数が2なので右端はpN/2
        while (L <= R) {
            pSyokou = (L + R) / 2;

            long wkSum = pKousuu * (pSyokou * 2 + pKousuu - 1) / 2;
            if (wkSum == pN) {
                Console.WriteLine("初項={0},項数={1},和={2}", pSyokou, pKousuu, pN);
                return true;
            }
            if (wkSum < pN)
                L = pSyokou + 1;
            else R = pSyokou - 1;
        }
        return false;
    }
}

C#でのデバッグ情報付の実行結果

初項=7,項数=2,和=15
初項=4,項数=3,和=15
初項=1,項数=5,和=15
12

C++のソース

#include <stdio.h>
#include <string>

bool ExecNibunhou(long long pN, long long pKousuu, long long &pSyokou);

std::string InputPattern = "Input2";

long long GetInput()
{
    if (InputPattern == "Input1") {
        return 18;
        //8
    }
    else if (InputPattern == "Input2") {
        return 15;
        //12
    }
    else if (InputPattern == "Input3") {
        return 105;
        //139
    }
    else if (InputPattern == "Input4") {
        return 256;
        //0
    }
    else if (InputPattern == "Input5") {
        return 945;
        //1698
    }
    else {
        long long ScanVal;
        int Dummy = scanf("%lld",&ScanVal);
        return ScanVal;
    }
}

int main()
{
    long long N = GetInput();
    long long Answer = 0;

    //項数でループ
    for (long long Kousuu = 2; ; Kousuu++) {
        //1から始めたとしても、オーバーならBreak
        long long wkSum = (Kousuu * (Kousuu + 1)) / 2;
        if (wkSum > N) break;

        long long Syokou;
        if (ExecNibunhou(N, Kousuu, Syokou)) {
            Answer += Syokou;
        }
    }
    printf("%lld\n",Answer);
}

//S = 項数 * (初項+初項+項数-1) /2
//は、初項に対して単調増加なので、初項を2分法で探す
bool ExecNibunhou(long long pN, long long pKousuu, long long &pSyokou)
{
    pSyokou = -1;
    long long L = 1;
    long long R = pN / 2; //最低項数が2なので右端はpN/2
    while (L <= R) {
        pSyokou = (L + R) / 2;

        long long wkSum = pKousuu * (pSyokou * 2 + pKousuu - 1) / 2;
        if (wkSum == pN) {
            printf("初項=%lld,項数=%lld,和=%lld\n",pSyokou, pKousuu, pN);
            return true;
        }
        if (wkSum < pN)
            L = pSyokou + 1;
        else R = pSyokou - 1;
    }
    return false;
}

解説

項数が3で初項が1なら、S = 1+2+3
項数が5で初項が10なら、S = 10+11+12+13+14
となり、一般化すると、等差数列の和の公式を使って
S = 項数 * (初項+末項) /2
  = 項数 * (初項+初項+項数-1) /2
となります。

Sは固定ですので、項数をループさせつつ、
数式を満たす初項が存在するかを、2分法で探してます。