yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) C - ABC conjecture

問題の要約
 正の整数Nが与えられる。
 A<=B<=CかつABC<=Nであるような正の整数の組(A,B,C)の個数を求めよ。
 制約上2^63未満であることが保証されている。
制約
 1<=N<=10^11
入力
 N

考え方
 1,A=1,B=1のとき,Cは1からNまでのN個ある。
  A=1,B=2のとき,Cは2からfloor(N/2)までのfloor(N/2)-1個ある。
  A=1,B=3のとき,Cは3からfloor(N/3)までのfloor(N/3)-2個ある。
  A=1,B=Nのとき,CはNからfloor(N/N)=1までなので,0個である。
   Bがどこまであるかというと,
  A=1,B=jのとき,Cはjからfloor(N/j)までのfloor(N/j)-(j-1)個あるので、floor(N/j)がjまである。
 2,A=2,B=2のとき,Cは2からfloor(N/(2*2))までのfloor(N/(2*2))-1個ある。
  A=2,B=3のとき,Cは3からfloor(N/(2*3))までのfloor(N/(2*3))-2個ある。
  A=2,B=Nのとき,CはNからfloor(N/(2*N))までなので,0個である。
   Bがどこまであるかというと,
  A=2,B=jのとき,Cはjからfloor(N/(2*j))までのfloor(N/(2*j))-(j-1)個あるので、floor(N/(2*j))がjまである。
 3,A=i,B=jのとき,Cはjからfloor(N/(i*j))までのfloor(N/(i*j))-(j-1)個ある。
   Bはfloor(N/(i*j))がjまである。
 4,Aはどこまであるかというと,A<=B<=Cより、ABCの一番大きい値はA=B=Cである。
  ABC<=NよりA^3<=N,A<=N^(1/3)である。
 5,これを素直に実装する。
long long count = 0;
for(long long A = 1; A <= pow(N, 1./3.); A++){
 for(long long B = A; B <= floor(N/(A*B)); B++){
  count += floor(N/(A*B))-(B+1);
 }
}
cout << count << endl;

 6,誤差に配慮して条件式を書き直す。
実際のプログラム
#include<iostream>
#include<cmath>
 
using namespace std;
 
int main(){
    long long N;
      cin >> N;
      long long count = 0;
      for(long long A = 1; A*A*A <= N; A++){
        for(long long B = A; A*B*B <= N; B++){
            count += floor(N/(A*B))-(B-1);
        }
    }
  
      cout << count << endl;
  
    return 0;
}