結果

問題 No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...
ユーザー titiatitia
提出日時 2021-01-23 15:30:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 609 ms / 2,000 ms
コード長 875 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 63,376 KB
最終ジャッジ日時 2024-12-30 21:08:55
合計ジャッジ時間 4,748 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
mod=10**9+7
from math import gcd
# .ax+by=gcd(a,b)(x,y)(x,y)gcd(x,y).
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1,a,b(1,0),(0,1)
# print(a,b,axy,bxy)
q,r=divmod(a,b)
if r==0:
return bxy,b # a*bxy[0]+b*bxy[1]=b
rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # r.
return Ext_Euc(b,r,bxy,rxy)
T=int(input())
for tests in range(T):
N,K,H,Y=map(int,input().split())
A=[N,K,H]
A.sort(reverse=True)
a,b,c=A
G_bc=gcd(b,c)
(x0,y0),G=Ext_Euc(b,c)
ANS=0
for i in range(Y//a+1):
rest=Y-i*a
if rest%G_bc!=0:
continue
ANS+=rest*x0//c+rest*y0//b+1
ANS%=mod
print(ANS)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0