結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー zeronosu77108
提出日時 2021-02-28 18:28:54
言語 Kotlin
(2.4.10 + ACL)
コンパイル:
kotlinc -cp /opt/aclib/ac_library.jar _filename_ -include-runtime -d main.jar
実行:
java -cp main.jar:/opt/aclib/ac_library.jar _class_
結果
WA  
実行時間 -
コード長 1,125 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,183 ms
コンパイル使用メモリ 504,124 KB
実行使用メモリ 45,040 KB
最終ジャッジ日時 2026-09-09 06:18:53
合計ジャッジ時間 16,554 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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