💡

ABC 103 C - Modulo Summationのメモ

2023/08/19に公開

AtCoder

競プロ

tech

解いてみました。

考察

$X\bmod Y$ の結果としてあり得るのは0から $Y - 1$ までです。例えば6なら0～5までがあり得ます。その中で最大なのは $Y - 1$ で、 $Y$ が6なら5です。これは $X$ がどんなに大きくなっても同じで、 $X$ が $Y$ の倍数の場合は余りは0、その倍数から1を引いた数だと $Y - 1$ で、これが余りとしては最大の値です。

なので、可能な限り多くの $a_N$ について、その数の倍数から1を引いた数となっているような $m$ が見つかれば解けます。
ここまで考えたら、あることに気づきました。可能な限り多くのというか、全ての $a_N$ について、倍数 - 1となる数は必ず存在するのではということです。別に最小公倍数とかでなくてもよくただの倍数でいいので、全ての $a_N$ をかけあわせた数は全ての $a_N$ の倍数となっており、ということはその数から1を引いた数は、まさに条件を満たす数なのではないかと。

そういうことであれば、 $a_1 - 1, a_2 - 1, ..., a_N - 1$ の合計値、つまり全ての $a_N$ それぞれに対して1を引いて、それを全部足せば答えになるのではと。
最初に書いた通り $X\bmod Y$ の最大値は $Y - 1$ なので、 $m\bmod a_N$ の最大値は $a_N - 1$ です。そして求める答えは、それらを全て足した数ということなので。

実装

そんなんでいいのかと少し心配しましたが、これで通りました。実際に $m$ を求めなくても、理想的な $m$ が必ず存在するとわかれば、その場合どうなるかはわかっているのでそれを計算するだけということですね。

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }

    println(a.map { it - 1 }.sum())
}

と言いつつ、実はその前に実際に $m$ を求める解法で提出していました。普通にやると巨大な数になってしまいオーバーフローするので、多倍長整数を使う必要がありましたが。

単純に全部かけ合わせるのではなく、最小公倍数を求めていけばオーバーフローしないかなと雑に考えたのですが、そんなことはなく…

import java.math.BigInteger

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toBigInteger() }

    val m = a.reduce { left, right ->
        lcm(left, right)
    } - BigInteger.ONE

    val list = a.map { m % it }

    var ans = BigInteger.ZERO
    for(i in list.indices) {
        ans += list[i]
    }

    println(ans)
}

fun gcd(a: BigInteger, b: BigInteger): BigInteger {
    return if (b == BigInteger.ZERO) {
        a
    } else {
        gcd(b, a % b)
    }
}

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

どうせ多倍長整数を使ってしまうなら、上に書いた通り単純に全部かけ合わせるのでもいいのではと思ってやってみたのがこちら。

import java.math.BigInteger

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toBigInteger() }

    val m = a.reduce { left, right ->
        left * right
    } - BigInteger.ONE

    val list = a.map { m % it }

    var ans = BigInteger.ZERO
    for(i in list.indices) {
        ans += list[i]
    }

    println(ans)
}

これでも普通に通りました。

（執筆時間: 26分25秒）

考察

実装

Discussion