答えを見たらもっと楽だった。
確認時の比を 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))
まず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))
