結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2023-11-23 03:21:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 867 ms / 2,000 ms |
コード長 | 1,425 bytes |
コンパイル時間 | 142 ms |
コンパイル使用メモリ | 81,852 KB |
実行使用メモリ | 90,576 KB |
最終ジャッジ日時 | 2024-09-26 07:51:22 |
合計ジャッジ時間 | 6,992 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter,deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _heappush_max(heap,item):heap.append(item)heapq._siftdown_max(heap, 0, len(heap)-1)def _heappushpop_max(heap, item):if heap and item < heap[0]:item, heap[0] = heap[0], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as GCDread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlineswrite=sys.stdout.write#import pypyjit#pypyjit.set_param('max_unroll_recursion=-1')#sys.set_int_max_str_digits(10**9)def Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yT=int(readline())mod=10**9+7for t in range(T):N,K,H,Y=map(int,readline().split())N,K,H=sorted([N,K,H])ans=0g=GCD(N,K)N//=gK//=gn,k=Extended_Euclid(N,K)for h in range(Y//H+1):YY=Y-h*Hif YY%g:continuenn=n*YY//gkk=k*YY//gans+=max(0,kk//N+1-(-nn+K-1)//K)ans%=modprint(ans)