コンテンツにスキップ

ABC480 E - Product-Bounded Arithmetic Sequences

サイト
AtCoder
コンテスト
ABC480
問題
E - Product-Bounded Arithmetic Sequences
難易度
1355

長さが 33 以上で、公差が正の、正整数からなる等差数列を良い数列と呼びます。良い数列のうち、要素の総積が NN 以下であるものの個数を求める問題です(1≤N≤10181 \le N \le 10^{18})。

良い数列は、長さ ll、初項 aa、公差 dd で決まります(l≥3l \ge 3、a≥1a \ge 1、d≥1d \ge 1)。総積は

a(a+d)(a+2d)⋯(a+(l−1)d)a (a + d) (a + 2d) \cdots (a + (l - 1)d)

です。答えは 101210^{12} 程度になる(入力例 2)ので 1 つずつ数えることはできませんが、ll と aa を全探索して、dd の個数をまとめて数えれば間に合います。

  • ll の範囲:総積が最小になるのは a=d=1a = d = 1 のときで、その値は l!l! です。20!≈2.4×1018>101820! \approx 2.4 \times 10^{18} > 10^{18} なので、l≤19l \le 19 です。
  • aa の範囲:総積は a3a^3 より大きいので、a<106a < 10^6 です。
  • dd の個数:ll と aa を決めると、総積は dd について単調増加です。よって総積が NN 以下になる dd は 11 以上のある値 DD 以下のすべての整数で、その個数 DD は二分探索で求められます。総積は 2d22d^2 より大きいので、D<109D < 10^9 です。

aa を大きくしても総積は増えるので、ある aa で D=0D = 0 になったら、それより大きい aa も調べる必要はありません。計算量は、l=3l = 3 のときの 10610^6 個の aa のそれぞれで二分探索をするのがいちばん重く、全体で 10810^8 回程度の計算です。

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 のときの総積が NN 以下か」なので、返り値がそのまま DD になります。f(0) が偽(つまり al>Na^l > N)のときも、すべての x で偽なので 00 が返り、D=0D = 0 として扱えます。

総積の計算では、saturating_mul で掛け算がオーバーフローしたときに long long の最大値に丸めています。

使用ライブラリ:cpp_include@9c33ee7