結果
問題 | No.546 オンリー・ワン |
ユーザー | Ryushi-tech |
提出日時 | 2020-06-20 20:12:05 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 963 bytes |
コンパイル時間 | 81 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-07-03 17:32:31 |
合計ジャッジ時間 | 946 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
from math import gcd, ceilimport itertools as itn, l, h = map(int, input().split())A = list(map(int, input().split()))G = [[] for _ in range(n + 1)]def divc(x, y):return ceil(x // y)if n == 1:print(divc(h, A[0]) - divc(l - 1, A[0]))exit()for g in it.product([0, 1], repeat=n):gc = g.count(1)if gc == 0 or gc == 1:continuetmp = []for i, gg in enumerate(g):if gg:tmp.append(A[i])res = tmp[0]for j in range(1, gc):res = res * tmp[j] // gcd(res, tmp[j])G[gc].append(res)def solve(z):ans = [[0] for _ in range(n + 1)]su = 0for a in A:su += divc(z,a)for i in range(1, n + 1):for gx in G[i]:ans[i][0] += divc(z, gx)for j, x in enumerate(ans):if any(j == c for c in [0, 1]):continuesign = j & 1su -= (-1)**sign * j * x[0]return suprint(solve(h) - solve(l - 1))