結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-23 03:42:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 722 ms / 2,000 ms |
コード長 | 701 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 64,484 KB |
最終ジャッジ日時 | 2024-12-29 14:06:36 |
合計ジャッジ時間 | 4,908 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import sysimport io, osinput = sys.stdin.buffer.readlinet = int(input())mod = 10**9+7def extgcd(a, b):# ax+by = gcd(x, y)の整数解を求める# x, y, gcd(a, b)を返すif b == 0:return 1, 0, aq, r = divmod(a, b)x, y, d = extgcd(b, r)s, t = y, x-q*yreturn s, t, dimport mathfor _ in range(t):n, k, h, y = map(int, input().split())n, k, h = sorted([n, k, h], reverse=True)g = math.gcd(k, h)a, b = k//g, h//gx0, y0, _ = extgcd(a, b)ans = 0for i in range(y//n+1):c = y-n*iif c%g:continuec = c//gans += (c*y0)//a-(-c*x0+b-1)//b+1ans %= modprint(ans)