結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 23:11:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,797 ms / 2,000 ms |
コード長 | 538 bytes |
コンパイル時間 | 746 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 232,724 KB |
最終ジャッジ日時 | 2024-09-16 13:30:40 |
合計ジャッジ時間 | 35,258 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
def gcd(a, b): while b: a, b = b, a % b return a N = int(input()) A = [int(a) for a in input().split()] nn = (N - 1).bit_length() X = [A] + [[0] * N for _ in range(nn)] for i in range(nn): for j in range(N - (1 << i + 1) + 1): X[i+1][j] = gcd(X[i][j], X[i][j + (1 << i)]) def calc(i, j): if i == j: return 0 a = (i - j).bit_length() - 1 return gcd(X[a][j], X[a][i-(1<<a)]) j = 0 ans = 0 for i in range(1, N + 1): while calc(i, j) == 1: j += 1 ans += i - j print(N * (N + 1) // 2 - ans)