結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-22 23:19:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,394 ms / 2,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 342 ms |
コンパイル使用メモリ | 81,808 KB |
実行使用メモリ | 75,980 KB |
最終ジャッジ日時 | 2024-12-28 07:28:24 |
合計ジャッジ時間 | 8,333 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
""""""import sysfrom sys import stdinimport mathdef extGCD2(a,b):if b:d,y,x = extGCD(b,a % b)y -= a // b * xreturn d,x,yreturn a,1,0def extGCD(a,b):g = math.gcd(a,b)x, y, u, v = 1, 0, 0, 1while b:k = a // bx -= k * uy -= k * vx, u = u, xy, v = v, ya, b = b, a % breturn g ,x, yTT = int(stdin.readline())mod = 10**9+7ans = 0for loop in range(TT):N,K,H,Y = map(int,stdin.readline().split())A = [N,K,H]A.sort()A.reverse()ans = 0aa,bb = A[1],A[2]gg,xx,yy = extGCD(aa,bb)for i in range(0,Y // A[0] + 1):rem = Y - A[0] * i#print (rem)a,b,g,x,y = aa,bb,gg,xx,yyif rem % g != 0:continuex *= rem // gy *= rem // glcm = a * b // gp = lcm // aq = lcm // b#xをp増やし、yをq減らす#xをp減らし、yをq増やす ができるif x >= 0:move = x // pxa,ya = x - move * p , y + move * qelse:move = (abs(x)+p-1) // pxa,ya = x + move * p , y - move * qif y >= 0:move = y // qxb,yb = x + move * p, y - move * qelse:move = (abs(y)+q-1) // qxb,yb = x - move * p , y + move * qif ya < 0 or xb < 0:continue#print (rem , xa , ya , xb , yb)ans += max(0 , (xb - xa) // p + 1)ans %= modprint (ans)