beta.atcoder.jp
答えを見たらもっと楽だった。
確認時の比を t : a、前回までの累計をT, A、前回確認時からの差分をx , yとしたとき以下が成り立てばよい。
T + x : A + y = t : a
式にしてこれを整理すると、
x = (t * A + y * t) / a - T
y = (a * T + x * a) / t - A
となる。このとき、x, y がいずれも0または正の整数となり、最少であればよい。
xの右辺のうち、Tは整数のため、残りの部分が分子がaで割り切れることが必要であり、
(t * A) % a = m
とすると、
(m + (y * t)) % a = 0
となるyを見つければよい。
さらに、x が0または正より
x = (t * A + y * t) / a - T >= 0
が成り立つため、
yについて整理すると、
y >= (T * a - t * A) / t
というyの条件ができる。y >= 0と合わせて、
これらの条件のうち大きいほうをyの検索範囲の最初にする。
ユークリッドの互除法とかをほんとは使いそうなんだけれども、
条件さえ決めてしまえば+1ずつしても間に合ってしまったのでそのまま提出。
周りの解答見るともう4倍ぐらい早いな。。
def solve(N, TAs):
T, A = 1, 1
for t, a in TAs:
m = (t * A) % a
y = max(0, (T * a - t * A) // t)
while True:
if (m + (y * t)) % a == 0:
break
y += 1
x = (t * A + t * y) // a - T
T += x
A += y
return T + A
if __name__ == "__main__":
N = int(input())
TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
print(solve(N, TAs))
beta.atcoder.jp
まずNの偶奇でAとして存在可能な数値が分かれる。
Nが偶数の時、Aの要素は奇数になり、それらはすべて2つずつ存在する。
Nが奇数の時、Aの要素は偶数になり、ちょうど真ん中にある0は一つ、それ以外はすべて二つずつ存在する。
以下でテストケースは通るんだけどAの要素の上限設定も必要だった。このままだと相異なればよいだけや。
from collections import Counter
def solve(N, As):
c = Counter(As)
n = 10 ** 9 + 7
if c['0'] == N % 2 and \
all([v == 2 and int(i) % 2 == (N + 1) % 2 for i, v in c.items() if i != '0']):
return pow(2, N // 2, n)
return 0
if __name__ == "__main__":
N = int(input())
As = input().split(" ")
print(solve(N, As))
