結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-25 01:13:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 701 ms / 2,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 643 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 67,088 KB |
最終ジャッジ日時 | 2024-07-23 11:54:03 |
合計ジャッジ時間 | 4,729 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
def f(a, b): """ ax + by = gcd(a,b) = d となる (x,y,d) を返す """ if b == 0: return (1, 0, a) q, r = a // b, a % b x, y, d = f(b, r) s, t = y, x - q * y return s, t, d #================================================ from math import gcd T=int(input()) for _ in range(T): N,K,H,Y=map(int,input().split()) assert 1<=N<=10**6,"Nが制約違反(N={})".format(N) assert 1<=K<=10**6,"Kが制約違反(N={})".format(K) assert 1<=H<=10**6,"Hが制約違反(N={})".format(H) assert 1<=Y<=10**12,"Yが制約違反(Y={})".format(Y) assert min(Y//N,Y//K,Y//H)<=10**6,"計算量が多すぎ(N={},K={},H={},Y={})".format(N,K,H,Y) N,K,H=sorted([N,K,H],reverse=True) Mod=10**9+7 Ans=0 g=gcd(K,H) A,B=K//g,H//g p,q,_=f(A,B) for x in range(0,Y//N+1): beta=Y-N*x if beta%g: continue S=beta//g upper=S*q//A lower=(-S*p+(B-1))//B Ans+=upper-lower+1 Ans%=Mod print(Ans)