ABC284-D Happy New Year 2023

問題へのリンク

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("3");
            WillReturn.Add("2023");
            WillReturn.Add("63");
            WillReturn.Add("1059872604593911");
            //17 7
            //3 7
            //104149 97711
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static List<long> mNList = new List<long>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        foreach (string EachStr in InputList.Skip(1)) {
            long N = long.Parse(EachStr);
            mNList.Add(N);
        }

        // エラトステネスの篩の上限を求める
        long MaxN = mNList.Max();
        long Jyougen = 1;
        while (Jyougen * Jyougen * Jyougen < MaxN) {
            Jyougen++;
        }
        Eratosthenes(Jyougen);

        mNList.ForEach(pX => Solve(pX));
    }

    static void Solve(long pN)
    {
        foreach (long EachSosuu in mSosuuArr) {
            if (pN % (EachSosuu * EachSosuu) == 0) {
                long Answer1 = EachSosuu;
                long Answer2 = pN / (EachSosuu * EachSosuu);
                Console.WriteLine("{0} {1}", Answer1, Answer2);
                break;
            }
            if (pN % EachSosuu == 0) {
                long Answer1 = LongSqrt(pN / EachSosuu);
                long Answer2 = EachSosuu;
                Console.WriteLine("{0} {1}", Answer1, Answer2);
                break;
            }
        }
    }

    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();
    }

    // 2分法でlong型のsqrtを求める
    static long LongSqrt(long pVal)
    {
        long L = 0;
        long R = pVal;
        var PairSet = new HashSet<string>();
        while (true) {
            if (PairSet.Add(string.Format("{0},{1}", L, R)) == false) {
                break;
            }
            long Mid = (L + R) / 2;
            if (Mid <= pVal / Mid) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}

解説

A,B,Cが0以上で
A+B+C = 300 の場合
A,B,Cの少なくとも1つは100以上です。

同様に
A,B,Cが1以上で
A*B*C = 1000 の場合
A,B,Cの少なくとも1つは10以上です。

同様に
D,Eが1以上で
D*D*E = 1000 の場合
D,Eの少なくとも1つは10以上です。

なので、Nの3乗根をエラトステネスの篩の上限として
素因数分解の一意性より
N = P*P*Q
のPかQのいずれかになってるかを判定してます。