AtCoderログ：0081 - ABC 057 C

問題

問題文

整数 $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)$ の最小値を求めてください。

制約

・$1 \le N \le 10^{10}$
・$N$ は整数である。

収録されている問題セット

• AtCoder に登録したら次にやること (第08問類題)

回答

回答1 (TLE)

$A,B$ は $N$ の約数なので、$A$ を $1$ から $N$ まで変化させ、$A$ が $N$ を割り切る場合に関数 $F(A,N/A)$ を計算し、その最小値を調べれば良いでしょう。コードは以下のようになります。なお自然数 $M$ の桁数は $\lfloor \log_{10}{M} \rfloor +1$ という計算によって求められます。

残念ながらこのコードは TLE となります。このコードの繰返し回数は $N$ 回で、その最大値は $10^{10}$ 回なので、時間内に処理できない場合が生じています。

abc057c-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n;
  cin >> n;

  int fmin;
  for ( int64_t a=1; a<=n; a++ ) {
    if ( n%a==0 ) {
      int f = max( floor(log10(a))+1, floor(log10(n/a))+1 );
      fmin = min( fmin, f );
    }
  }

  cout << fmin << endl;
}

回答2 (AC)

回答1では、例えば $A=1$ のときに $F(A,B)=F(1,N)$ を計算する一方で、$A=N$ のときに $F(A,B)=F(N,1)$ と同じものを計算しており、効率が悪いです。そこで $A$ が $N/A$ より小さい場合に限定することで、上記のような繰り返し計算を避けることが出来ます。$A \le N/A$ を整理すると $A \le \sqrt{N}$ となるので、変数 $A$ は $\sqrt{N}$ まで変化させれば良いことがわかります。$A \le N/A$ であることから、$F(A,N/A)$ は常に $N/A$ の桁数を調べれば良いこともわかります。

これらの考察を用いたコードは以下のようになります。

abc057c-2.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int64_t n;
  cin >> n;

  int fmin = floor(log10(n))+1;
  for ( int a=2; a<=floor(sqrt(n)); a++ ) {
    if ( n%a==0 ) {
      fmin = min( fmin, (int)floor(log10(n/a))+1 );
    }
  }

  cout << fmin << endl;
}

このコードの繰り返し回数は $\sqrt{N}$ 回なので、最大繰返し回数は $\sqrt{10^{10}}=10^5$ 回となり、十分処理可能であることがわかります。

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答2と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0080 - ABC 214 B