結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー zeronosu77108
提出日時 2021-02-28 18:28:54
言語 Kotlin
(2.1.0)
結果
WA  
実行時間 -
コード長 1,125 bytes
記録
コンパイル時間 13,388 ms
コンパイル使用メモリ 437,028 KB
実行使用メモリ 52,100 KB
最終ジャッジ日時 2024-10-02 21:47:41
合計ジャッジ時間 21,918 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:25:17: warning: variable 'y' is never used
        val (x, y, d) = ext_gcd(n, m); // x is inv of n/d (mod. m/d)
                ^

ソースコード

diff #
raw source code 

//
// Created by zeronosu77108 on 2021/02/28.
//
import kotlin.collections.*
import kotlin.math.*

@kotlin.ExperimentalStdlibApi
fun main() {
    val (x1, y1) = readLine()!!.split(" ").map { it.toLong() }
    val (x2, y2) = readLine()!!.split(" ").map { it.toLong() }
    val (x3, y3) = readLine()!!.split(" ").map { it.toLong() }

    val (ans, _) = crt(mutableListOf((x1 to y1), (x2 to y2), (x3 to y3)))
    println(ans ?: -1)
}

/**
 * Chinese remainder theorem（）
 * @param am 連立合同式  z ≡ x (mod m1) : (x, m1)
 * @return (z, m) x ≡ z (mod m)
 */
fun crt(am : List<Pair<Long, Long>>) : Pair<Long?, Long?> {
    var r = 0L; var n = 1L
    for ((a, m) in am) {
        val (x, y, d) = ext_gcd(n, m); // x is inv of n/d (mod. m/d)
        if ((a - r) % d != 0L) return null to null
        val tmp = (a - r) / d * x % (m/d);
        r += n * tmp;
        n *= m / d;
    }
    return (r%n+n)%n to n
}

fun ext_gcd(a : Long, b : Long) : Triple<Long, Long, Long> {
    return when(b) {
        0L -> Triple(1L,0L, a)
        else -> { val (x, y, g) = ext_gcd(b, a%b); return Triple(y , x - a/b * y, g) }
    }
}
0