結果
問題 | 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 % breturn aN = 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 0a = (i - j).bit_length() - 1return gcd(X[a][j], X[a][i-(1<<a)])j = 0ans = 0for i in range(1, N + 1):while calc(i, j) == 1:j += 1ans += i - jprint(N * (N + 1) // 2 - ans)