結果

問題 No.186 中華風 (Easy)
ユーザー zeronosu77108zeronosu77108
提出日時 2021-02-28 18:28:54
言語 Kotlin
(1.9.23)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 300 ms
51,808 KB
testcase_01 AC 296 ms
51,648 KB
testcase_02 AC 298 ms
51,696 KB
testcase_03 AC 311 ms
51,556 KB
testcase_04 AC 308 ms
51,560 KB
testcase_05 AC 310 ms
51,564 KB
testcase_06 AC 298 ms
51,696 KB
testcase_07 AC 298 ms
51,716 KB
testcase_08 AC 295 ms
51,524 KB
testcase_09 AC 293 ms
51,572 KB
testcase_10 AC 299 ms
51,636 KB
testcase_11 AC 305 ms
51,636 KB
testcase_12 AC 302 ms
51,564 KB
testcase_13 AC 314 ms
51,628 KB
testcase_14 AC 309 ms
51,756 KB
testcase_15 AC 312 ms
51,656 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 308 ms
51,832 KB
testcase_19 AC 305 ms
51,868 KB
testcase_20 AC 302 ms
51,660 KB
testcase_21 AC 295 ms
51,760 KB
testcase_22 AC 304 ms
51,680 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 # 

//
// 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