結果
問題 | No.62 リベリオン(Extra) |
ユーザー |
![]() |
提出日時 | 2023-04-12 01:22:16 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 432 ms / 5,000 ms |
コード長 | 1,759 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-10-07 21:12:00 |
合計ジャッジ時間 | 1,552 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 |
ソースコード
import sysinput = sys.stdin.readlinefrom 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)q,r=divmod(a,b)if r==0:return bxy,b # a*bxy[0]+b*bxy[1]=brxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.return Ext_Euc(b,r,bxy,rxy)# 中国剰余定理(拡張ユークリッドの互除法を使う)def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbのときN=k mod(lcm(ma,mb))なるk,lcm(ma,mb)を返す.(p,q),d=Ext_Euc(ma,mb)if (a-b)%d!=0:return -1 # 解がないとき-1を出力return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//ddef calc(W,H,D,Mx,My,Hx,Hy,Vx,Vy):GCD=gcd(Vx,Vy)D*=GCDVx//=GCDVy//=GCDGx=gcd(Vx,2*W)if (Mx-Hx)%Gx!=0:return FalseVx=Vx//Gxmx=(Mx-Hx)//GxDx=2*W//GxGy=gcd(Vy,2*H)if (My-Hy)%Gy!=0:return FalseVy=Vy//Gymy=(My-Hy)//GyDy=2*H//Gy#print((mx*pow(Vx,-1,Dx),Dx,my*pow(Vy,-1,Dy),Dy))kx=Chirem(mx*pow(Vx,-1,Dx),Dx,my*pow(Vy,-1,Dy),Dy)if kx==-1:return Falsek,GCD=kxif k<=D:return TrueQ=int(input())for tests in range(Q):W,H,D,Mx,My,Hx,Hy,Vx,Vy=map(int,input().split())flag=0if calc(W,H,D,Mx,My,Hx,Hy,Vx,Vy)==True:flag=1if calc(W,H,D,-Mx,My,Hx,Hy,Vx,Vy)==True:flag=1if calc(W,H,D,Mx,-My,Hx,Hy,Vx,Vy)==True:flag=1if calc(W,H,D,-Mx,-My,Hx,Hy,Vx,Vy)==True:flag=1if flag==0:print("Miss")else:print("Hit")