[ABC227] C - ABC conjecture
[Q] https://atcoder.jp/contests/abc227/tasks/abc227_c
同じ問題をatcoderで見たことがある気がする。3回目かも。
[これ] https://atcoder.jp/contests/arc113/submissions/27448860
2乗根、3乗根の誤差バグを踏みました(1WA)
1. Aが許されるのは、A*A*A <= N を満たす範囲まで。
2. Bが許されるのは、A*B*B <= N を満たす範囲まで。
AとBは全探索。
3. Cが許されるのは、B以上、N/(A*B)以下。
Cは計算で範囲を求めます。
4パターンの結果をメモしておく。
[264ms AC] Aの上限を積で判定する。 a*a*a<=N
int main(){
cincout();
ll N;
cin >> N;
ll ans = 0;
for(ll a=1; a*a*a<=N; ++a){
for(ll b=a; a*b*b<=N; ++b){
ans += N/a/b - b + 1;
}
}
cout << ans << endl;
}
[852ms AC] sqrtl(), cbrtl() を使う。 エスキューアールティー「エル」。
for(ll a=1; a<=cbrtl(N); ++a){
for(ll b=a; b<=sqrtl(N/a); ++b){
ans += N/a/b - b + 1
[589ms AC] sqrtl(), cbrtl() を使う。Cをa*bで割って求める。
for(ll a=1; a<=cbrtl(N); ++a){
for(ll b=a; b<=sqrtl(N/a); ++b){
ans += N/(a*b) - b + 1;
[WA] sqrt(), cbrt() を使うと、1WAくらう。何のケースかは知らない
for(ll a=1; a<=cbrt(N); ++a){
for(ll b=a; b<=sqrt(N/a); ++b){
ans += N/a/b - b + 1;
Q. sqrt?
A. 脳内でスクエアルートって読んでます。2乗根。
cbrt は キューブルートって読んでます。3乗根。
https://atcoder.jp/contests/abc227/submissions/27216450