二種類のバス [yukicoder 894]

https://yukicoder.me/problems/no/894

解説

https://yukicoder.me/submissions/384924

出発回数を計算するが、包除原理を用いる。
(バス1が出発 または バス2が出発) = (バス1が出発) + (バス2が出発) - (バス1が出発 かつ バス2が出発)
これをそれぞれ計算する。

「バス1が出発」の組み合わせは、(T-1)/A+1となる。
同様に「バス2が出発」の組み合わせは、(T-1)/B+1となる。
どちらも出発する組み合わせは、lcm(A,B)時間に出発するものなので、(T-1)/lcm(A,B)+1である。

注意点として、A,Bが10¹⁸と大きいので普通にlcm(A,B)を取るとオーバーフローしてしまう。
オーバーフロー対策がなされているlcmを使おう。

ll T, A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> A >> B;

    ll go1 = (T - 1) / A + 1;
    ll go2 = (T - 1) / B + 1;
    ll go12 = (T - 1) / lcm(A, B) + 1;

    ll ans = go1 + go2 - go12;
    cout << ans << endl;
}