ABC400-E Ringo's Favorite Numbers 3

問題へのリンク

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("5");
            WillReturn.Add("404");
            WillReturn.Add("36");
            WillReturn.Add("60");
            WillReturn.Add("1000000000000");
            WillReturn.Add("123456789");
            //400
            //36
            //36
            //1000000000000
            //123454321
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mMaxA;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList.Skip(1).Select(pX => long.Parse(pX)).ToArray();

        mMaxA = AArr.Max();

        long PLimit = 1;
        while (PLimit * PLimit * PLimit * PLimit <= mMaxA) {
            PLimit++;
        }

        long QLimit = 1;
        while (2 * 2 * QLimit * QLimit <= mMaxA) {
            QLimit++;
        }

        Eratosthenes(QLimit);

        var AnswerSet = new HashSet<long>();
        for (long I = 0; I <= mSosuuArr.GetUpperBound(0); I++) {
            if (mSosuuArr[I] > PLimit) break;
            List<long> BekiList1 = DeriveBekiList(mSosuuArr[I]);

            for (long J = I + 1; J <= mSosuuArr.GetUpperBound(0); J++) {
                List<long> BekiList2 = DeriveBekiList(mSosuuArr[J]);

                foreach (long EachBeki1 in BekiList1) {
                    foreach (long EachBeki2 in BekiList2) {
                        if (WillOverProd(EachBeki1, EachBeki2, mMaxA)) {
                            break;
                        }
                        else {
                            AnswerSet.Add(EachBeki1 * EachBeki2);
                        }
                    }
                }
            }
        }

        long[] AnswerArr = AnswerSet.ToArray();
        Array.Sort(AnswerArr);

        foreach (long EachA in AArr) {
            int ResultInd = ExecNibunhou_LowerOrEqual_Max(EachA, AnswerArr);
            long Answer = AnswerArr[ResultInd];
            Console.WriteLine(Answer);
        }
    }

    static List<long> DeriveBekiList(long pBase)
    {
        var WillReturn = new List<long>();

        long Beki = pBase * pBase;
        long CurrVal = Beki;
        while (true) {
            WillReturn.Add(CurrVal);

            if (WillOverProd(CurrVal, Beki, mMaxA)) {
                break;
            }
            CurrVal *= Beki;
        }

        return WillReturn;
    }

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

    static long[] mSosuuArr;

    // エラトステネスの篩
    static void Eratosthenes(long pJyougen)
    {
        bool[] IsSosuuArr = new bool[pJyougen + 1];
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            IsSosuuArr[I] = true;
        }
        for (int I = 2; I * I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) {
                for (int J = I * 2; J <= IsSosuuArr.GetUpperBound(0); J += I) {
                    IsSosuuArr[J] = false;
                }
            }
        }

        var SosuuList = new List<long>();
        for (int I = 2; I <= IsSosuuArr.GetUpperBound(0); I++) {
            if (IsSosuuArr[I]) SosuuList.Add(I);
        }

        mSosuuArr = SosuuList.ToArray();
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static int ExecNibunhou_LowerOrEqual_Max(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pArr.Last()) {
            return pArr.GetUpperBound(0);
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pArr[0]) {
            return -1;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pArr[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

N = 素数Pの偶数乗 * 素数Qの偶数乗
なので、クエリを先読みして、
Nの最大値を求め、MaxAとおきます。

素数P < 素数Q とすれば
素数P * 素数P * 素数P * 素数P <= MaxA
2 * 2  * 素数Q * 素数Q <= MaxA
の二つの不等式が成り立つので、
素数Pと素数Qの上限が求まります。

あとは、エラトステネスの篩で
Q以下の素数を列挙してから、
解候補をナイーブに列挙し、各クエリに回答することができます。