ABC400-C 2^a b^2

問題へのリンク

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("20");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("400");
            //24
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1234567890");
            //42413
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

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

        long Answer = 0;

        // Aを全探索
        int Cnt = 0;
        long Beki2 = 2;
        while (true) {
            long CurrAnswer = DeriveAnswer(Beki2);
            if (CurrAnswer == 0) break;
            Answer += CurrAnswer;
            Beki2 *= 2;
            if (++Cnt == 2) break;
        }
        Console.WriteLine(Answer);
    }

    // 2べきを引数として、Bの上限を返す
    static long DeriveAnswer(long pBeki2)
    {
        // 1の場合
        if (CanAchieve(pBeki2, 1) == false) {
            return 0;
        }

        long L = 1;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (CanAchieve(pBeki2, Mid)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // N以下にできるかを返す
    static bool CanAchieve(long pBeki2, long pB)
    {
        long Prod = pBeki2;
        if (WillOverProd(Prod, pB, mN)) {
            return false;
        }
        Prod *= pB;

        if (WillOverProd(Prod, pB, mN)) {
            return false;
        }
        Prod *= pB;

        return true;
    }

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

解説

2^a * b^2
なので aを全探索し、
bの上限を二分探索することを考えます

N = 2^1 * 平方数
N = 2^2 * 平方数
N = 2^3 * 平方数
N = 2^4 * 平方数
N = 2^5 * 平方数
N = 2^6 * 平方数
N = 2^7 * 平方数
N = 2^8 * 平方数
でNを重複カウントしてしますので
代表を決めて、重複カウントを防ぐことを考えます。

すると
N = 2^1 * 平方数
N = 2^2 * 平方数
N = 2^3 * 平方数 = 2^1 * 2^2 * 平方数
N = 2^4 * 平方数 = 2^2 * 2^2 * 平方数
N = 2^5 * 平方数 = 2^1 * 2^4 * 平方数
N = 2^6 * 平方数 = 2^2 * 2^4 * 平方数
N = 2^7 * 平方数 = 2^1 * 2^6 * 平方数
N = 2^8 * 平方数 = 2^2 * 2^6 * 平方数

指数法則より
2^4は(2^2)の2乗
2^6は(2^3)の2乗
です

なので
N = 2^1 * 平方数
N = 2^2 * 平方数
の通り数の和が、解だと分かります。