ABC480 E - Product-Bounded Arithmetic Sequences
- サイト
- AtCoder
- コンテスト
- ABC480
- 問題
- E - Product-Bounded Arithmetic Sequences
- 難易度
- 1355
長さが 以上で、公差が正の、正整数からなる等差数列を良い数列と呼びます。良い数列のうち、要素の総積が 以下であるものの個数を求める問題です()。
良い数列は、長さ 、初項 、公差 で決まります(、、)。総積は
です。答えは 程度になる(入力例 2)ので 1 つずつ数えることはできませんが、 と を全探索して、 の個数をまとめて数えれば間に合います。
- の範囲:総積が最小になるのは のときで、その値は です。 なので、 です。
- の範囲:総積は より大きいので、 です。
- の個数: と を決めると、総積は について単調増加です。よって総積が 以下になる は 以上のある値 以下のすべての整数で、その個数 は二分探索で求められます。総積は より大きいので、 です。
を大きくしても総積は増えるので、ある で になったら、それより大きい も調べる必要はありません。計算量は、 のときの 個の のそれぞれで二分探索をするのがいちばん重く、全体で 回程度の計算です。
C++
#include "shogo-library/base/all"#include "shogo-library/math/saturating.hpp"#include "shogo-library/utility/binary-search.hpp"
void solve() { LL(N); ll ans = 0; rep(l, 3, 20) { rep(a, 1, 1e6) { ll ng = 1e9; ll ok = binary_search(0, ng, [=](ll x) { ll p = a, t = a; rep(l - 1) { t += x; p = saturating_mul(p, t); if (p > N) break; } return p <= N; }); if (ok == 0) break; ans += ok; } } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ここでは f(x) が「公差 x のときの総積が 以下か」なので、返り値がそのまま になります。f(0) が偽(つまり )のときも、すべての x で偽なので が返り、 として扱えます。
総積の計算では、saturating_mul で掛け算がオーバーフローしたときに long long の最大値に丸めています。
使用ライブラリ:cpp_include@9c33ee7