結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー | 👑 Kazun |
提出日時 | 2023-08-20 11:20:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,322 ms / 2,000 ms |
コード長 | 2,305 bytes |
コンパイル時間 | 591 ms |
コンパイル使用メモリ | 87,132 KB |
実行使用メモリ | 76,948 KB |
最終ジャッジ日時 | 2023-08-20 11:20:17 |
合計ジャッジ時間 | 9,751 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 93 ms
75,796 KB |
testcase_01 | AC | 78 ms
71,424 KB |
testcase_02 | AC | 76 ms
71,396 KB |
testcase_03 | AC | 78 ms
71,364 KB |
testcase_04 | AC | 77 ms
71,372 KB |
testcase_05 | AC | 97 ms
71,584 KB |
testcase_06 | AC | 105 ms
75,820 KB |
testcase_07 | AC | 105 ms
76,044 KB |
testcase_08 | AC | 103 ms
76,056 KB |
testcase_09 | AC | 102 ms
76,224 KB |
testcase_10 | AC | 100 ms
75,988 KB |
testcase_11 | AC | 1,204 ms
76,920 KB |
testcase_12 | AC | 1,079 ms
76,596 KB |
testcase_13 | AC | 1,322 ms
76,784 KB |
testcase_14 | AC | 961 ms
76,948 KB |
testcase_15 | AC | 1,067 ms
76,776 KB |
testcase_16 | AC | 1,210 ms
75,892 KB |
ソースコード
#拡張ユークリッドの互除法 def Find_Extend_Euclid(a: int, b: int): """ gcd(a,b) と ax+by=gcd(a,b) を満たす整数 x,y の例を挙げる. [Input] a,b: 整数 [Output] (x,y,gcd(a,b)) """ s,t,u,v=1,0,0,1 while b: q,a,b=a//b,b,a%b s,t=t,s-q*t u,v=v,u-q*v return s,u,a def Solve_Bezout_Identity(a, b, c, lx, rx, ly, ry, extgcd = None): """ a x + b y = c , lx <= x <= rx, ly <= y <= ry を満たすような整数の組 (x,y) を求める. [Input] a != 0, b != 0 lx <= rx, ly <= ry extgcd: (s,t) の形のタプルであり, a s + b t = gcd(a, b) でなくてはならない. [Output] 存在しない場合, (None, None, None, None, None, None) 存在する場合, (p0, p1, q0, q1, lk, rk) の形のタプルである. 以下を意味する. x = p0 + p1 k, y = q0 + q1 k, lk <= k <= rk """ assert a != 0 and b != 0 assert lx <= rx and ly <= ry if extgcd is None: s, t, g = Find_Extend_Euclid(a, b) else: s, t = extgcd g = a * s + b * t if c % g != 0: return (None, None, None, None, None, None) a //= g; b //= g; c //=g if b > 0: tmp_l = lx - c * s tmp_r = rx - c * s else: tmp_l = -(rx - c * s) tmp_r = -(lx - c * s) klx = (tmp_l + abs(b) - 1) // abs(b) krx = tmp_r // abs(b) if a > 0: tmp_l = -ry + c * t tmp_r = -ly + c * t else: tmp_l = -(-ly + c * t) tmp_r = -(-ry + c * t) kly = (tmp_l + abs(a) - 1) // abs(a) kry = tmp_r // abs(a) kl = max(klx, kly); kr = min(krx, kry) if kl > kr: return (None, None, None, None, None, None) return (c * s, b, c * t, -a, kl, kr) #================================================== def solve(): N, K, H, Y = map(int, input().split()) N, K, H = sorted([N, K, H]) s, t, _ = Find_Extend_Euclid(N, K) inf = float("inf") ans = 0 for z in range(0, Y // H + 1): _, _, _, _, l, r = Solve_Bezout_Identity(N, K, Y - H * z, 0, Y, 0, Y, (s, t)) if l is not None: ans += r - l + 1 return ans % (10**9 + 7) #================================================== T = int(input()) print(*[solve() for _ in range(T)], sep = "\n")