中国剰余定理

crt.kt

// https://qiita.com/drken/items/ae02240cd1f8edfc86fd
// https://github.com/NASU41/AtCoderLibraryForJava/blob/132179385293fd6c0d522d73f3f48435967fffcb/Math/MathLib.java

fun mod(a: Long, m: Long): Long {
    val x = a % m
    return if (x < 0) x + m else x
}

fun extGCD(a: Long, b: Long): LongArray {
    if (b == 0L) {
        return longArrayOf(a, 1, 0)
    }
    val (d, y, x) = extGCD(b, a % b)
    return longArrayOf(d, x, y - a / b * x)
}

fun invGcd(a: Long, b: Long): LongArray {
    val va = mod(a, b)
    if (va == 0L) return longArrayOf(0, 0)
    var s = b
    var t = va
    var m0 = 0L
    var m1 = 1L
    while (t > 0) {
        val u = s / t
        s -= t * u
        m0 -= m1 * u
        s = t.also { t = s }
        m0 = m1.also { m1 = m0 }
    }
    if (m0 < 0) m0 += b / s
    return longArrayOf(s, m0)
}

fun crt(b1: Long, b2: Long, m1: Long, m2: Long): LongArray {
    val (d, p) = extGCD(m1, m2) // d is gcd(m1, m2), p is inv of m1/d (mod. m2/d)
    if ((b2 - b1) % d != 0L) return longArrayOf(0, 0)
    val m = m1 * (m2 / d) // lcm of (m1, m2)
    val tmp = (b2 - b1) / d * p % (m2 / d)
    val r = mod(b1 + m1 * tmp, m)
    return longArrayOf(r, m)
}

fun crt(r: List<Long>, m: List<Long>): LongArray {
    assert(r.size == m.size)
    val n = r.size
    var r0 = 0L
    var m0 = 1L
    for (i in 0 until n) {
        assert(1 <= m[i])
        var r1 = mod(r[i], m[i])
        var m1 = m[i]
        if (m0 < m1) {
            r0 = r1.also { r1 = r0 }
            m0 = m1.also { m1 = m0 }
        }
        if(m0 % m1 == 0L){
            if(r0 % m1 != r1) return longArrayOf(0, 0)
            continue
        }
        val (g, im) = invGcd(m0, m1)
        val u = m1 / g
        if((r1 - r0) % g != 0L) return longArrayOf(0, 0)
        val x = (r1 - r0) / g % u * im % u
        r0 += x * m0
        m0 *= u
        if(r0 < 0) r0 += m0
    }
    return longArrayOf(r0, m0)
}