遊び倒すガイド 中級編 1から9までの数字が1度ずつ現れる平方根

問題

344 という数は面白い性質を持っている。
344 の平方根を小数表示した sqrt(344) = 18.547236990・・・ は、
小数点を無視すると、先頭の9桁に1から9までの数字が1度ずつ現れる。
344 はこのような性質を持つ最も小さな整数である。

31078 もこの性質を持つ。sqrt(31078) = 176.28953457・・・である。
31078 はこの性質を持つ10番目に小さな整数である。

この性質を持つ160万番目に小さな整数を求めよ。

プロジェクトオイラーを遊び倒すガイド (中級編)

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew(); 
        
        int OKCnt = 0;
        long I = 1;

        while (true) {
            bool WillSkip;
            long NextI;
            if (IsOK(I, out WillSkip, out NextI)) {
                OKCnt++;
                if (OKCnt == 1 || OKCnt % 50000 == 0)
                    Console.WriteLine("{0}はOK,現在のOK数={1},経過時間={2}", I, OKCnt, sw.Elapsed);
                if (OKCnt == 1600000) return;
            }
            if (WillSkip) I = NextI;
            else I++;
        }
    }

    static bool IsOK(long pTarget, out bool pWillSkip, out long pNextI)
    {
        pWillSkip = false;
        double SqrtVal = Math.Sqrt(pTarget);

        int Seisuubu = (int)Math.Truncate(SqrtVal);
        pNextI = (long)(Seisuubu + 1) * (long)(Seisuubu + 1);
        int KetasuuSeisuubu = DeriveKetasuu(Seisuubu);
        double Jyousuu = DeriveJyousuu(KetasuuSeisuubu);

        int Syousuubu = (int)((SqrtVal - Seisuubu) * Jyousuu);
        int KetasuuSyousuubu = DeriveKetasuu(Syousuubu);

        var NumList = new List<int>(9);
        
        do {
            int WillAdd = Seisuubu % 10;
            if (WillAdd == 0 || NumList.Contains(WillAdd)) {
                pWillSkip = true;
                return false;
            }

            NumList.Add(WillAdd);
            if (NumList.Count == 9) return true;
        } while ((Seisuubu /= 10) > 0);

        do {
            int WillAdd = Syousuubu % 10;
            if (WillAdd == 0) return false;
            if (NumList.Contains(WillAdd)) return false;

            NumList.Add(WillAdd);
            if (NumList.Count == 9) return true;
        } while ((Syousuubu /= 10) > 0);

        return false;
    }

    static int DeriveKetasuu(int pVal)
    {
        if (pVal < 10) return 1;
        if (pVal < 100) return 2;
        if (pVal < 1000) return 3;
        if (pVal < 10000) return 4;
        if (pVal < 100000) return 5;
        if (pVal < 1000000) return 6;
        if (pVal < 10000000) return 7;
        if (pVal < 100000000) return 8;
        return 9;
    }

    static double DeriveJyousuu(int pVal)
    {
        if (pVal == 1) return 100000000D;
        if (pVal == 2) return 10000000D;
        if (pVal == 3) return 1000000D;
        if (pVal == 4) return 100000D;
        if (pVal == 5) return 10000D;
        if (pVal == 6) return 1000D;
        if (pVal == 7) return 100D;
        return 10D;
    }
}

実行結果

省略
3421224772はOK,現在のOK数=1400000,経過時間=00:02:56.8631831
3525089231はOK,現在のOK数=1450000,経過時間=00:03:02.9115144
3765028090はOK,現在のOK数=1500000,経過時間=00:03:09.1619161
3861202491はOK,現在のOK数=1550000,経過時間=00:03:15.4133262
3951343689はOK,現在のOK数=1600000,経過時間=00:03:21.6461511

解説

121の平方根は 11
144の平方根は 12
ですので、11のように、整数部だけでパンデジタル数でないことが確定する場合は、
整数部に1足した数の平方である144までループをSkipさせてます。