結果

問題 No.186 中華風 (Easy)
ユーザー 👑 zeronosu77108zeronosu77108
提出日時 2021-02-28 18:28:54
言語 Kotlin
(1.9.23)
結果
WA  
実行時間 -
コード長 1,125 bytes
コンパイル時間 10,540 ms
コンパイル使用メモリ 439,592 KB
実行使用メモリ 57,264 KB
最終ジャッジ日時 2024-04-12 10:05:34
合計ジャッジ時間 17,867 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 269 ms
56,964 KB
testcase_01 AC 259 ms
56,996 KB
testcase_02 AC 256 ms
57,160 KB
testcase_03 AC 256 ms
57,144 KB
testcase_04 AC 285 ms
56,992 KB
testcase_05 AC 256 ms
56,960 KB
testcase_06 AC 257 ms
57,100 KB
testcase_07 AC 256 ms
57,144 KB
testcase_08 AC 260 ms
57,244 KB
testcase_09 AC 261 ms
56,980 KB
testcase_10 AC 254 ms
57,212 KB
testcase_11 AC 259 ms
57,004 KB
testcase_12 AC 269 ms
56,964 KB
testcase_13 AC 254 ms
57,084 KB
testcase_14 AC 256 ms
57,096 KB
testcase_15 AC 259 ms
57,120 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 255 ms
56,984 KB
testcase_19 AC 267 ms
57,000 KB
testcase_20 AC 260 ms
57,084 KB
testcase_21 AC 256 ms
57,104 KB
testcase_22 AC 255 ms
57,116 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