トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ABC-057-C Digits in Multiplication

■■■問題■■■

整数Nが与えられます。
ここで、2つの正の整数A,Bに対して、
F(A,B) を「10進表記における、Aの桁数とBの桁数のうち大きい方」と定義します。
例えば、F(3,11) の値は、3は1桁、11は2桁であるため、F(3,11)=2 となります。

2つの正の整数の組 (A,B) が N= A×B を満たすように動くとき、
F(A,B)の最小値を求めてください。

■■■入力■■■

N

●1 <= N <= 100億
●Nは整数である

■■■出力■■■

2つの正の整数の組 (A,B) が N=A×B を満たすように動くときの
F(A,B) の最小値を出力せよ。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("10000");
            //3
            //(A,B)=(100,100)のときにF(A,B)は最小値をとるため、
            //F(100,100) = 3 を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000003");
            //7
            //条件を満たす(A,B)の組は(1,1000003)と(1000003,1)の2通りで、
            //F(1,1000003) = F(1000003,1) = 7 です。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9876543210");
            //6
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //試し割りで約数を列挙
        int Answer = int.MaxValue;
        for (long I = 1; I * I <= N; I++) {
            if (N % I == 0) {
                long YakuSuu1 = I;
                long YakuSuu2 = N / I;

                int KetaSuu1 = DeriveKetaSuu(YakuSuu1);
                int KetaSuu2 = DeriveKetaSuu(YakuSuu2);

                int CurrVal = Math.Max(KetaSuu1, KetaSuu2);
                if (CurrVal < Answer)
                    Answer = CurrVal;
            }
        }
        Console.WriteLine(Answer);
    }

    //桁数を求める
    static int DeriveKetaSuu(long pVal)
    {
        if (pVal <= 9) return 1;
        if (pVal <= 99) return 2;
        if (pVal <= 999) return 3;
        if (pVal <= 9999) return 4;
        if (pVal <= 99999) return 5;
        if (pVal <= 999999) return 6;
        if (pVal <= 9999999) return 7;
        if (pVal <= 99999999) return 8;
        if (pVal <= 999999999) return 9;
        if (pVal <= 9999999999) return 10;
        return 11;
    }
}


解説

試し割りで約数かを判定してます。