キーエンスプログラミングコンテスト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;
}