ABC 341

Table of Contents

D - Only one of two

https://atcoder.jp/contests/abc341/tasks/abc341_d

解説 AC

$x$ 以下の整数のうち $N$, $M$ のいずれか一方のみで割り切れるものの個数を $f(x)$ とすると

\begin{align*} f(x) = \floor{\frac{x}{N}} + \floor{\frac{x}{M}} - 2 \cdot \floor{\frac{x}{\text{lcm}(N, M)}} \end{align*}

である。

$f(x) \geq K$ となる最小の $x$ を二分探索で求めれば良い。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M, K;
    cin >> N >> M >> K;

    auto f = [&](ll x) -> ll {
        ll numn = x / N;
        ll numm = x / M;
        ll numc = x / lcm(N, M);

        return numn + numm - numc * 2;
    };

    ll wa = 0, ac = INF;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj) >= K)
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

E - Alternating String

https://atcoder.jp/contests/abc341/tasks/abc341_e

解説 AC