天下一プログラマーコンテスト2017 C 4/N

■■■問題■■■

整数Nが与えられる。
4/N = 1/h + 1/n + 1/w を満たす正整数 h,n,w を求めよ。
条件を満たす解が複数ある場合、どれを出力しても良い。

■■■入力■■■

N

●Nに対して h,n,w <= 3500 となる解が存在することが保証される

■■■出力■■■

条件を満たす正整数 h,n,w の組を空白区切りで1つ出力せよ。
h n w

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //1 2 2
            // 4/2 = 1/1 + 1/2+ 1/2 である
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3485");
            //872 1012974 1539173474040
            //解として3500を超える整数を使っても良い
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4664");
            //3498 3498 3498
        }
        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]);

        for (long B = 1; B <= 3500; B++) {
            for (long C = B; C <= 3500; C++) {
                long wkBunsi = -N * B * C;
                long wkBunbo = -4 * B * C + N * C + N * B;

                if (wkBunbo == 0) continue;
                if (wkBunsi % wkBunbo != 0) continue;
                long wkA = wkBunsi / wkBunbo;
                if (wkA <= 0) continue;

                Console.WriteLine("{0} {1} {2}", wkA, B, C);
                return;
            }
        }
    }
}

解説

下記のように、Aについて方程式を解いて、
1以上3500以下の、BとCの組み合わせを全探索してます。
(BとCについて対称なので、B <= C としてます)

4/N = 1/A + 1/B + 1/C
4/N = (BC+AC+AB) / ABC
4ABC = NBC + A*(NC+NB)
-NBC = -4ABC + A*(NC+NB)
-NBC = A*(-4BC + NC + NB)
A = (-NBC) / (-4BC + NC + NB)