ARC-034-B 方程式

■■■問題■■■

正整数nに対し、nの十進表記における各桁の数の和をf(n)で表す。
例えば、f(123)=1+2+3=6, f(4)=4となる。

正整数Nが与えられる。
等式 x+f(x)=N を満たす正整数xを全て求めよ。

■■■入力■■■

N

1行目に、1個の整数 N (1 <= N <= 10の18乗) が与えられる。

■■■出力■■■

等式を満たす正整数xの値の個数をkとする。
1行目にkの値を出力し、続くk行に等式を満たす正整数xの値を昇順で各行に1個ずつ出力せよ。
末尾の改行を忘れないこと。

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("8");
            //1
            //4
            //問題文で述べたように f(4)=4 であり、
            //4以外に題意を満たす正整数は存在しない。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("101");
            //2
            //91
            //100
            //複数の解が存在することがある
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("108");
            //0
            //解が存在しないこともある
        }
        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]);

        //Nは10の18乗までなので、9*17が最大の桁和となる
        const long MaxKetaSum = 9 * 17;

        var AnswerList = new List<long>();
        for (long I = N - MaxKetaSum; I <= N; I++) {
            if (I + DeriveKetaSum(I) == N) {
                AnswerList.Add(I);
            }
        }
        Console.WriteLine(AnswerList.Count);
        AnswerList.ForEach(X => Console.WriteLine(X));
    }

    //桁の数字の和を求める
    static long DeriveKetaSum(long pVal)
    {
        long WillReturn = 0;
        do {
            long ModVal = pVal % 10;
            WillReturn += ModVal;
            pVal /= 10;
        } while (pVal > 0);
        return WillReturn;
    }
}

解説

xの下限を数学的に考察して、計算量を減らしてます。