コンテンツにスキップ

競プロキャンプ2026関西 A - km - n = k

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
A - km - n = k

整数 XX が与えられます。1≤k,m,n≤X1 \le k, m, n \le X を満たす整数の組 (k,m,n)(k, m, n) のうち、km−n=kkm - n = k を満たすものの個数を求める問題です(2≤X≤1062 \le X \le 10^6)。

km−n=kkm - n = k は n=k(m−1)n = k(m - 1) と変形できます。nn は kk と mm から決まるので、nn が 11 以上 XX 以下になるような (k,m)(k, m) の組を数えればよいです。

t=m−1t = m - 1 とおくと、条件は 1≤t≤X−11 \le t \le X - 1 かつ kt≤Xkt \le X です(kt≥1kt \ge 1 は t≥1t \ge 1 から成り立ちます)。kk を固定すると、条件を満たす tt は 11 以上 min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) 以下のすべての整数です。これを k=1,…,Xk = 1, \dots, X について足し合わせれば答えです。

⌊X/k⌋\lfloor X / k \rfloor は割り算で直接求められますが、下のコードでは「kt≤Xkt \le X を満たす最大の tt」を二分探索で求めています。計算量は O(Xlog⁡X)O(X \log X) です。

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 が上の t=m−1t = m - 1 です。binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ng を XX にしているので、返り値は XX 未満で kt≤Xkt \le X を満たす最大の tt、つまり min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) です。k≤Xk \le X なので、f(1) は常に真です。

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