ABC227 C - ABC conjecture C++解答例

ABC227 C - ABC conjectureをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

正の整数$N$が与えられます。
$A \leq B \leq C$かつ$ABC \leq N$であるような正の整数の組$(A, B, C)$の個数を求めてください。
なお、制約の条件下で答えは$2^{63}$未満であることが保証されます。

制約

• $1 \leq N \leq 10^{11}$
• $N$は整数である

解答例

工夫した全探索で解く

正の整数の組$(A, B, C)$を全探索して個数を数え上げることを考えます。
問題文の条件より、3つの数のうち一番小さい$A$を決め打ちすると、他の2つの数の大きさは$A$以上になることがわかります。
したがって、$A$を決め打ちしたとき、3つの数の積$ABC$の大きさは必ず$A^3$以上になります。

このことから、3つの数の積$ABC$が$N$以下になるような組み合わせを全探索したいわけですが、$A$を決め打ちしたとき、すでに$N < A^3$となってしまうような$A$は探索しなくてもよいことになります。
これで$A$の探索範囲を$1 \leq A \leq \sqrt[3]{N}$と決めることができました。

次に$B$の探索範囲を決めます。$A$の値が決定されているとき、$B$の値は$A$以上を取ります。また、$B$の値が決まったとき$C$が取れる値は$B$以上です。
したがって、$B$が取れる値の範囲は$A^3 \leq A \times B^2 \leq N$、すなわち$A \leq B \leq \sqrt{\frac{N}{A}}$となります。

次に$C$の探索範囲を決めるのですが、$A, B$の2つの値が決まったとき、問題文の条件より$C$の取れる最大値は$\lfloor \frac{N}{A \times B} \rfloor$と計算することができます。最大値がわかったので、$C$は1から$\lfloor \frac{N}{A \times B} \rfloor$までの値を取ることができるとわかります。
ただし、$C$の値は$B$以上でなければなりません。そのため、$C$の取れる値は1以上$\lfloor \frac{N}{A \times B} \rfloor$以下の値のうち、$B$未満の値を取り除いた値になります。数式で表すと$\lfloor \frac{N}{A \times B} \rfloor - B + 1$です。

実装例

実際の実装例を以下に示します。$C$の場合の数を計算する際の床関数ですが、C++では整数の割り算を行ったときに小数点以下が切り捨てられる(床関数と同じ動作をする)ので特に何も考えずに実装できます。

c.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
int main() {
  int64_t N;
  std::cin >> N;
 
  int64_t count = 0;
  // Aの値を全探索する
  for (int64_t i = 1; i * i * i <= N; i++) {
    // Bの値を全探索する
    for (int64_t j = i; i * j * j <= N; j++) {
      // AとBを決めればCが取れる値の場合の数が決まる
      count += N / (i * j) - j + 1;
    }
  }
 
  std::cout << count << std::endl;
 
  return 0;
}

実際に提出したコードはこちら。