結果

問題 No.3068 Speedrun (Hard)
ユーザー SPD_9X2
提出日時 2025-03-24 19:54:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,338 ms / 2,000 ms
コード長 2,128 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 65,552 KB
最終ジャッジ日時 2025-03-24 19:54:53
合計ジャッジ時間 12,882 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

cR + dS = trem
c+d = nrem

cR + (nrem-c)S = trem

(R-S)c = trem-nremS

"""

import sys
import math
def extGCD(a,b):
    g = math.gcd(a,b)
    x, y, u, v = 1, 0, 0, 1
    while b:
        k = a // b
        x -= k * u
        y -= k * v
        x, u = u, x
        y, v = v, y
        a, b = b, a % b
    return g ,x, y

def extinv(a,mod):
    g,x,y = extGCD(a,mod)
    if g != 1:
        return -1
    if x > 0:
        return x
    else:
        return x + mod

# X^K = Y (mod M)
from math import ceil, sqrt
def BsGs(X,Y,M): 

    dic = {}
    dic[1] = 0

    sq = ceil(M**0.5)

    #baby-step
    
    Z = 1
    for i in range(sq):
        Z = Z * X % M
        if Z not in dic:
            dic[Z] = i+1

    if Y in dic:
        return dic[Y]

    #giant-step

    R = extinv(Z,M)
    for i in range(1,sq+1):
        Y = Y * R % M
        if Y in dic:
            return dic[Y] + i * sq

    return -1

def crt2(b1,m1,b2,m2):
    g,p,q = extGCD(m1,m2)
    if b1 % g != b2 % g:
        return 0,0
    return ( b1 + m1 * ((b2-b1)//g) * p ) % (m1*m2//g) , m1*m2//g

def crt(b,m):
    assert len(b) == len(m)
    nb,nm = 0,1
    for i in range(len(b)):
        nb,nm = crt2(nb,nm,b[i],m[i])
        if (nb,nm) == (0,0):
            return 0,0
    return nb,nm



A,B,C,D,N = map(int,input().split())
P,Q,R,S,T = map(int,input().split())

g = math.gcd(R,S)
_,X,Y = extGCD(R,S)

for a in range(A+1):
    for b in range(B+1):

        trem = T - a * P - b * Q
        if trem % g != 0 or trem < 0:
            continue

        nrem = N - a - b
        if nrem < 0:
            continue
        
        # (R-S)c = trem-nremS

        if R != S:
            if (trem-nrem*S) % (R-S) != 0:
                continue
            c = (trem-nrem*S) // (R-S)
            d = nrem - c
        else:
            c = min(C, trem//R)
            d = nrem-c

        # print (a,b,c,d,(a + b + c + d == N) , 0 <= c <= C , 0 <= d <= D , a*P + b*Q + c*R + d*S == T)
        
        if (a + b + c + d == N) and 0 <= c <= C and 0 <= d <= D and a*P + b*Q + c*R + d*S == T:
            print (a,b,c,d)
            sys.exit()
0