🔥

ABC 131 C - Anti-Divisionのメモ

2022/09/14に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

考察

~~※たぶん間違ってますが、どこが間違っているかわからないため将来の自分に託します~~
※修正して、たぶん今は合っていると思います

全探索だと計算量はO(N)です。O(N)なら解ける問題は多くありますが、この問題の場合はNが大きすぎるので全然間に合いません。

ポイントは割り切れない整数自体を出力する必要はなく、個数を数えるだけでいいということです。
割り切れない整数を数えるのは大変ですが、割り切れる整数の個数なら割り算で求められます。
たとえば1以上100以下の整数のうち20で割り切れる整数は20、40、60、80、100の5つで、これは100 ÷ 20 = 5と一致します。
100個の整数のうち5個が割り切れる整数なので、割り切れない整数は単純に引いて95個とわかります。

それで、この問題の場合は「C でも D でも割り切れないもの」なので2つの数について考える必要があります。基本的にはそれぞれの数について割り切れる数を求めればいいのですが、それだけだと問題があります。
たとえば1以上100以下の整数のうち20でも30でも割り切れない数を求めるとすると、20で割り切れる数は5つ、30で割り切れる数は3つで、両方を100から引くと92です。しかし、20でも30でも割り切れる数として60があり、60を2回カウントして引いてしまっています。なので、その分を除外した93個が実際の答えです。
（20もしくは30で割り切れる数は20、30、40、60、80、90、100の7つ）

両方の数で割り切れる数とは、要するに公倍数です。公倍数の個数は除外して考えないといけません。では公倍数の数はどうやって求めればいいでしょうか？
公倍数とは、最小公倍数の倍数です。上の例だと20でも30でも割り切れる数は60しかないですが、この60が20と30の最小公倍数です。
もうちょっと範囲を広くして、200までの数を考えるとします。100までは考えたので101から200までで考えます。まずその範囲で30で割り切れる数は120、150、180の3つです。このうち20でも割り切れるのは120と180です。これは最小公倍数である60の倍数でもありますね。なので、公倍数の数は最小公倍数で割り切れる数を数えればいいです。これは最初で考えたのと同じで、その数で割った個数です。（余りは無視する）
1以上200以下の整数で60で割り切れる数は200 ÷ 60の商と同じ3です。

あともう一歩です。ここまで1以上の数で考えていましたが、実際には1以上とは限りません。たとえば23以上かもしれません。
この場合、1から22までの数は数えてはいけないので、22を引いて考える必要があります。
1以上100以下の整数で20でも30でも割り切れない数は、20もしくは30で割り切れる数は20、30、40、60、80、90、100の7つを引いた93個でした。93から22を引いてみると71です。しかし、これは実際の答えとは異なります。除外した1から22までの数の中に20が含まれるからです。この20の分余計に引いてしまっています。なので、実際には22を引くのではなく、20を除外した21を引く必要があります。なので、93から21を引いた72が答えです。

【追記】
ちょっとこの辺が怪しくて、「A未満の数は除外するが、A未満の数うちCかDで割り切れる数は除外しない」ではなく「A未満の数のうちCでもDでも割り切れない数は除外する」と考えるほうがよさそうです。
（それで実装をバグらせてました）

ここまで考察すれば解けそうです。

提出コード

すみません偉そうに書いておきながらアレですが、自分で実装したやつだと一つ目のサンプルが合わなくて結局解説を見ました…
内容的には上記の追記の通りの実装になっているはずです。

「B以下の数のうちCでもDでも割り切れない数の個数」と「A未満の数のうちCでもDでも割り切れない数の個数」を求める必要がありますが、処理としては同じなので関数化します。

lcmは最小公倍数です。最大公約数（gcd）を使って求めます。gcdのアルゴリズムはユークリッドの互除法です。
ここの計算量がネックになってTLEでは意味がないですが、この辺りは典型アルゴリズムなのでそれっぽいところから拝借しました。

fun main() {
    val (a, b, c, d) = readLine()!!.split(" ").map { it.toLong() }

    val allOfNotMultiple = countNotMultiple(b, c, d)

    val multipleA = countNotMultiple(a - 1, c, d)

    println(allOfNotMultiple - multipleA)
}

fun countNotMultiple(n: Long, c: Long, d: Long): Long {
    val cMultiple = n / c
    val dMultiple = n / d

    val lcm = lcm(c, d)

    val cdMultiple = n / lcm

    return n - cMultiple - dMultiple + cdMultiple
}

fun gcd(a: Long, b: Long): Long {
    return if (b == 0L) {
        a
    } else {
        gcd(b, a % b)
    }
}

fun lcm(a: Long, b: Long): Long {
    val d = gcd(a, b)
    return a / d * b;
}

考察

提出コード

Discussion