結果

問題 No.1036 Make One With GCD 2
ユーザー yudedakoyudedako
提出日時 2022-01-11 11:51:08
言語 Kotlin
(2.1.0)
結果
TLE  
実行時間 -
コード長 1,289 bytes
コンパイル時間 13,849 ms
コンパイル使用メモリ 446,000 KB
実行使用メモリ 303,828 KB
最終ジャッジ日時 2024-11-14 11:35:25
合計ジャッジ時間 70,702 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 34 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

tailrec fun gcd(a: Long, b: Long): Long {
return when(b){
0L -> a
else -> gcd(b, a % b)
}
}
fun Int.floorLog2(): Int {
var rest = this
var result = 0
for (d in 4 downTo 0) {
if (rest >= (1 shl (1 shl d))) {
rest = rest shr (1 shl d)
result += 1 shl d
}
}
return result
}
fun main() {
val n = readLine()!!.trim().toInt()
val num = readLine()!!.trim().split(' ').map(String::toLong)
val table = mutableListOf(num)
while ((1 shl table.size) <= n) {
val len = 1 shl table.size
val dest = mutableListOf<Long>()
for (i in 0 .. n - len) {
dest.add(gcd(table.last()[i], table.last()[i + len / 2]))
}
table.add(dest)
}
fun readTable(from: Int, until: Int): Long {
val len = until - from
if (len == 0) return 0L
val log2 = len.floorLog2()
return gcd(table[log2][from], table[log2][from + len - (1 shl log2)])
}
var j = 0
var result = 0L
for (i in 0 until n) {
var d = readTable(i, j)
while (j in num.indices && d != 1L) {
d = gcd(d, num[j])
j += 1
}
if (d == 1L) {
result += n - j + 1
}
}
println(result)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0