結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー | 👑 箱 |
提出日時 | 2020-10-10 03:48:26 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 396 ms / 2,000 ms |
コード長 | 2,125 bytes |
コンパイル時間 | 17,247 ms |
コンパイル使用メモリ | 420,192 KB |
実行使用メモリ | 53,840 KB |
最終ジャッジ日時 | 2023-09-30 14:47:31 |
合計ジャッジ時間 | 21,689 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 256 ms
50,640 KB |
testcase_01 | AC | 257 ms
50,444 KB |
testcase_02 | AC | 261 ms
50,404 KB |
testcase_03 | AC | 260 ms
50,660 KB |
testcase_04 | AC | 262 ms
50,224 KB |
testcase_05 | AC | 271 ms
50,588 KB |
testcase_06 | AC | 270 ms
50,476 KB |
testcase_07 | AC | 268 ms
50,204 KB |
testcase_08 | AC | 339 ms
53,496 KB |
testcase_09 | AC | 341 ms
53,236 KB |
testcase_10 | AC | 340 ms
53,380 KB |
testcase_11 | AC | 360 ms
53,840 KB |
testcase_12 | AC | 341 ms
52,960 KB |
testcase_13 | AC | 288 ms
51,304 KB |
testcase_14 | AC | 396 ms
51,116 KB |
testcase_15 | AC | 338 ms
53,188 KB |
ソースコード
import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.io.PrintWriter import java.util.* import java.math.BigInteger fun PrintWriter.solve(sc: FastScanner) { val t = sc.nextInt() for (_i in 0 until t) { val n = sc.nextLong() if (n == 1L) { println(1) continue } val m = 2 * n - 1 val phi = phi(m) var ans = Long.MAX_VALUE val number = phi val div = mutableListOf<Long>() var divisor = 1L while (divisor * divisor <= number) { if (number % divisor == 0L) { div.add(divisor) if (divisor * divisor != number) { div.add(number / divisor) } } divisor++ } for (d in div) { if (modpow(2, d, m) == 1L) { ans = minOf(ans, d) } } println(ans) } } fun phi(n: Long): Long { var res = n var i = 2L var m = n while (i * i <= m) { if (m % i == 0L) { res = res / i * (i - 1) while (m % i == 0L) { m /= i } } i++ } if (m > 1) { res = res / m * (m - 1) } return res } fun modpow(a: Long, n: Long, m: Long): Long { if (n == 0L) return 1 if (n == 1L) return a val pow = modpow(a, n / 2, m) var res = pow * pow % m if (n % 2 == 1L) { res *= a res %= m } return res } fun main() { val writer = PrintWriter(System.out, false) writer.solve(FastScanner(System.`in`)) writer.flush() } class FastScanner(s: InputStream) { private var st = StringTokenizer("") private val br = BufferedReader(InputStreamReader(s)) fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine() fun nextDouble() = next().toDouble() fun ready() = br.ready() }