ABC114-D 756

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("9");
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            //543
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var KaijyouSoinsuuDict = new SortedDictionary<int, int>();
        for (int I = 2; I <= N; I++) {
            Dictionary<int, int> CurrSoinsuuDict = DeriveSoinsuuDict(I);
            foreach (var EachPair in CurrSoinsuuDict) {
                if (KaijyouSoinsuuDict.ContainsKey(EachPair.Key) == false) {
                    KaijyouSoinsuuDict[EachPair.Key] = 0;
                }
                KaijyouSoinsuuDict[EachPair.Key] += EachPair.Value;
            }
        }

        // 場合の数[約数の数]なDP表
        int UB = 75;
        int[] DPArr = new int[UB + 1];
        DPArr[1] = 1;

        foreach (var EachSoinsuu in KaijyouSoinsuuDict) {
            for (int I = UB; 1 <= I; I--) {
                if (DPArr[I] == 0) continue;

                for (int J = 1; J <= EachSoinsuu.Value; J++) {
                    int NewInd = I * (J + 1);
                    if (NewInd > UB) break;
                    DPArr[NewInd] += DPArr[I];
                }
            }

            //Console.WriteLine("■■■DP結果■■■");
            //for (int I = 1; I <= UB; I++) {
            //    if (DPArr[I] > 0) {
            //        Console.WriteLine("DPArr[{0}]={1}", I, DPArr[I]);
            //    }
            //}
        }
        Console.WriteLine(DPArr[UB]);
    }

    // 素因数分解し、指数[素数]なDictを返す
    static Dictionary<int, int> DeriveSoinsuuDict(int pTarget)
    {
        var WillReturn = new Dictionary<int, int>();

        int CurrVal = pTarget;
        // ルートより大きい数を、素因素に持つとしても、1つだけのため
        // ルートまで試し割りを行い、素因数が残っていたら、追加する
        for (int I = 2; I * I <= pTarget; I++) {
            if (CurrVal % I > 0) continue;

            WillReturn[I] = 0;
            while (CurrVal % I == 0) {
                WillReturn[I]++;
                CurrVal /= I;
            }
            if (CurrVal == 1) break;
        }

        // 素因数が残っている場合
        if (CurrVal > 1) {
            WillReturn[CurrVal] = 1;
        }
        return WillReturn;
    }
}

解説

素因数分解してから、動的計画法を使ってます。