競プロキャンプ2026関西 A - km - n = k
- サイト
- MOFE
- コンテスト
- 競プロキャンプ2026関西
- 問題
- A - km - n = k
整数 が与えられます。 を満たす整数の組 のうち、 を満たすものの個数を求める問題です()。
は と変形できます。 は と から決まるので、 が 以上 以下になるような の組を数えればよいです。
とおくと、条件は かつ です( は から成り立ちます)。 を固定すると、条件を満たす は 以上 以下のすべての整数です。これを について足し合わせれば答えです。
は割り算で直接求められますが、下のコードでは「 を満たす最大の 」を二分探索で求めています。計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/utility/binary-search.hpp"
void solve() { LL(X); ll ans = 0; rep(k, 1, X + 1) { ans += binary_search(1, X, [=](ll mm) { return k * mm <= X; }); } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}mm が上の です。binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ng を にしているので、返り値は 未満で を満たす最大の 、つまり です。 なので、f(1) は常に真です。
使用ライブラリ:cpp_include@9c33ee7