結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 23:14:04 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 1,411 ms / 2,000 ms |
コード長 | 3,075 bytes |
コンパイル時間 | 18,176 ms |
コンパイル使用メモリ | 456,036 KB |
実行使用メモリ | 111,596 KB |
最終ジャッジ日時 | 2024-09-16 13:33:38 |
合計ジャッジ時間 | 55,098 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
import java.io.BufferedReaderimport java.io.InputStreamimport java.io.InputStreamReaderimport java.util.*import kotlin.math.absimport kotlin.math.maximport kotlin.math.minval MOD = 1_000_000_007Ltailrec fun gcd(a: Long, b: Long): Long {if (a < b) return gcd(b, a)if (b == 0L) return areturn gcd(b, a % b)}class Solver(stream: InputStream, private val out: java.io.PrintWriter) {fun solve() {val N = ni()val A = nal(N)fun dfs(l: Int, r: Int): Long {if (r - l == 1) {return if (A[l] == 1L) 1 else 0}var res = 0Lval med = (l + r) / 2val L = mutableListOf<Long>()var cur = 0Lfor (i in med - 1 downTo l) {cur = gcd(cur, A[i])L += cur}cur = 0var p = L.size - 1for (i in med until r) {cur = gcd(cur, A[i])while(p >= 0 && gcd(cur, L[p]) == 1L) {p--}debug{"$l:$r med:$med r:$i cnt:${L.size - p - 1}"}res += L.size - p - 1}res += dfs(l, med)res += dfs(med, r)return res}out.println(dfs(0, N))}private val isDebug = try {// なんか本番でエラーでるSystem.getenv("MY_DEBUG") != null} catch (t: Throwable) {false}private var tokenizer: StringTokenizer? = nullprivate val reader = BufferedReader(InputStreamReader(stream), 32768)private fun next(): String {while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {tokenizer = StringTokenizer(reader.readLine())}return tokenizer!!.nextToken()}private fun ni() = next().toInt()private fun nl() = next().toLong()private fun ns() = next()private fun na(n: Int, offset: Int = 0): IntArray {return map(n) { ni() + offset }}private fun nal(n: Int, offset: Int = 0): LongArray {val res = LongArray(n)for (i in 0 until n) {res[i] = nl() + offset}return res}private fun na2(n: Int, offset: Int = 0): Array<IntArray> {val a = Array(2){IntArray(n)}for (i in 0 until n) {for (e in a) {e[i] = ni() + offset}}return a}private inline fun map(n: Int, f: (Int) -> Int): IntArray {val res = IntArray(n)for (i in 0 until n) {res[i] = f(i)}return res}private inline fun debug(msg: () -> String) {if (isDebug) System.err.println(msg())}private fun debug(a: LongArray) {debug { a.joinToString(" ") }}private fun debug(a: IntArray) {debug { a.joinToString(" ") }}private fun debug(a: BooleanArray) {debug { a.map { if (it) 1 else 0 }.joinToString("") }}private fun debugDim(A: Array<IntArray>) {if (isDebug) {for (a in A) {debug(a)}}}/*** 勝手にimport消されるのを防ぎたい*/private fun hoge() {min(1, 2)max(1, 2)abs(-10)}}fun main() {val out = java.io.PrintWriter(System.out)Solver(System.`in`, out).solve()out.flush()}