square869120コンテスト2 B問題 Division 2

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("7 2");
            WillReturn.Add("3");
            WillReturn.Add("6");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 2");
            WillReturn.Add("6");
            WillReturn.Add("3");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 4");
            WillReturn.Add("4");
            WillReturn.Add("8");
            WillReturn.Add("16");
            WillReturn.Add("32");
            //2
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("50 4");
            WillReturn.Add("8");
            WillReturn.Add("6");
            WillReturn.Add("4");
            WillReturn.Add("3");
            //9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mN = wkArr[0];

        var AList = new List<long>();
        foreach (string EachStr in InputList.Skip(1)) {
            string CurrStr = Regex.Replace(EachStr, "[^0-9]", "");
            if (Regex.IsMatch(CurrStr, "^[0-9]+$")) {
                AList.Add(long.Parse(CurrStr));
            }
        }
        mAArr = AList.ToArray();

        long[] ProdArr = ExecDFS();

        foreach (long EachA in mAArr) {
            for (long I = 0; I <= ProdArr.GetUpperBound(0); I++) {
                if (ProdArr[I] % EachA == 0) {
                    ProdArr[I] /= EachA;
                }
            }
        }
        Console.WriteLine(ProdArr.Count(pX => pX == 1));
    }

    struct JyouaiDef
    {
        internal int CurrInd;
        internal long CurrProd;
    }

    static long[] ExecDFS()
    {
        var WillReturn = new List<long>();

        var Stk = new Stack<JyouaiDef>();
        JyouaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.CurrProd = 1;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyouaiDef Popped = Stk.Pop();
            WillReturn.Add(Popped.CurrProd);

            for (int I = Popped.CurrInd; I <= mAArr.GetUpperBound(0); I++) {
                WillPush.CurrInd = I + 1;
                if (WillOverProd(Popped.CurrProd, mAArr[I], mN)) {
                    continue;
                }
                WillPush.CurrProd = Popped.CurrProd * mAArr[I];
                Stk.Push(WillPush);
            }
        }
        return WillReturn.Distinct().ToArray();
    }

    // 2正数の掛け算が、Limitを超えるかを返す
    static bool WillOverProd(long pA, long pB, long pLimit)
    {
        return pA > pLimit / pB;
    }
}

解説

考察すると
割ったことで1になることの必要条件は、
aの配列の、1つ以上の要素の積であることだと分かります。

なので、
1つ以上の積をDFSで列挙してから
割れたら割る走査を、ナイーブにシュミレーションして、解くことができます。