mitchan5
@mitchan5 (hiro Minami)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

for文の条件式の制約

Q&A

Closed

下記の問題を回答したいです。初心者の質問で申し訳ないのですが、教えていただきたいです。

正の整数 N が与えられます。

A≤B≤C かつ ABC≤N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2 ^63未満であることが保証されます。

制約
1≤N≤10 ^11
N は整数である

発生している問題・エラー

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t A, B, C, N, count;
  cin >> N ;
  
  
  for(C=1; C <= N; C++){
    for(B=1; ((B <= C) && (B*C <= N)); B++){
    for(A=1; ((A <= B) && (A*B*C <= N)); A++){
      count++;
    }}}
  
  cout << count << endl;
}



### 自分で試したこと
上記のプログラムで回答が求まりません。
プログラムは動きます。forの条件文に問題があるのかと思い、条件を減らしてみたり、いろいろしましたがわかりませんでし
0

2Answer

jkr_2255さんの解答,変数countの初期化がなされていないことによる不定値の出力に補足で解答します.

もちろんそのコードは動くのですが,実行時間が気になりました.

入力の制約条件は$1\leq N\leq 10^{11}, N\in \mathbb{Z}$な上に,答えは$2^{63}\approx 9.2\times 10^{18}$未満であることが示されています.

これらを数え上げるのに,コンピュータではどのぐらいの時間を要するのかという議論の中で,既によく知られている指標として,1秒間に$10^7\sim 10^8$回ぐらいのforループの処理ができるというものがあります.

入力の制約条件の最大値$10^{11}$が与えられることを想定したとき,1秒当たりのforループの処理回数$10^7\sim 10^8$で除算すると,$10^3\sim 10^4$秒,すなわち16分から2.7時間ほどの処理時間になることを補足しておきます.

おそらくこの課題は,mitchan5さんの書いたような愚直解法で実行される線形時間以上の計算量を許さず,それ未満の実行時間で答えを求めることのできるアルゴリズムを要求しているように思います.

アルゴリズムとその計算量に関する話は以下の記事を参考にしてください.

ちなみにこの記事の1章3節の3番目の表に大ヒントがありますので一部抜粋しておきます.

サイズ $N$ 可能な計算量 アルゴリズム例 備考
$10^{9}~10^{12}$ $O(\log{n})$ 二分探索など $O(\sqrt{n})$ も有効です。

また,参考までにAtCoderの類題を載せておきます.

2Like

Comments

  1. @mitchan5

    Questioner

    とても丁寧に回答いただきありがとうございます!!!
    馬鹿な質問でした!またお願いします
  2. 解決されてよかったです。
    計算量削減,頑張ってくださいませ。

countを初期化していませんので、値が不定です。最初にcount = 0;としておきましょう。

1Like

Comments

  1. @mitchan5

    Questioner

    回答いただきありがとうございます!
    精進いたします。。。

Your answer might help someone💌