川添さん問題10 アフター・ドット

■■■問題■■■

自然数 n に対し、1 <= a <= n, 1 <= b <= n を満たし、
かつ小数で表した a÷b が有限小数となるような自然数の組 (a, b) の個数を F(n) と定義します。
(有限小数 ・・・ 小数点以下の桁数が有限である小数)

例えば、F(3) ＝ 7 です。
下記の(a, b)の組のうち、有限小数は赤字で記した7個です。

●1÷1＝1,　1÷2＝0.5,　1÷3＝0.33333・・・
●2÷1＝2,　2÷2＝1,　　2÷3＝0.66666・・・
●3÷1＝3,　3÷2＝1.5,　3÷3＝1

同様に、F(5)＝21 , F(10)＝68 , F(100)＝2185 となることが確かめられます。

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

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("3");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            //21
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            //68
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100");
            //2185
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("10000");
            //最悪計算量
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[] SosuuArr;

    //エラトステネスの篩で上限以下の素数の配列を作成
    static void Eratosthenes(int pJyougen)
    {
        var IsSosuuArr = new System.Collections.BitArray(pJyougen + 1);
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I] == false) continue;
            for (int J = I * 2; J <= IsSosuuArr.Count - 1; J += I) {
                IsSosuuArr[J] = false;
            }
        }
        var SosuuList = new List<int>();
        for (int I = 2; I <= IsSosuuArr.Count - 1; I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }
        SosuuArr = SosuuList.ToArray();
    }

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

        Eratosthenes(N);

        //自然数の個数[2と5以外の素因数の積]なDict
        var ProdValDict = new SortedList<int, int>();

        for (int I = 1; I <= N; I++) {
            int wkKey = DeriveProdVal(I);
            if (ProdValDict.ContainsKey(wkKey))
                ProdValDict[wkKey]++;
            else ProdValDict[wkKey] = 1;
        }

        int Answer = 0;
        foreach (var EachPair1 in ProdValDict) {
            foreach (var EachPair2 in ProdValDict) {
                //分子 < 分母 ならBreak
                if (EachPair1.Key < EachPair2.Key) break;

                //分子が分母の倍数なら有限小数
                if (EachPair1.Key % EachPair2.Key == 0) {
                    //積の法則
                    Answer += EachPair1.Value * EachPair2.Value;
                }
            }
        }
        Console.WriteLine(Answer);
    }

    //2と5以外の素因数の積を求める
    static int DeriveProdVal(int pTarget)
    {
        int WillReturn = 1;
        for (int I = 0; I <= SosuuArr.GetUpperBound(0); I++) {
            while (pTarget % SosuuArr[I] == 0) {
                pTarget /= SosuuArr[I];
                if (SosuuArr[I] != 2 && SosuuArr[I] != 5) {
                    WillReturn *= SosuuArr[I];
                }
            }
            if (pTarget < SosuuArr[I]) break;
        }
        return WillReturn;
    }
}

解説

各自然数を、2と5以外の素因数の積に、変換してから、
割り算の結果が有限小数になるかを判定してます。

ProdValDictの2重ループで、
SortedDictionaryだと1.5秒かかって処理が、
SortedListに変えると半分になりました。
列挙は、SortedListに分があるようですね。