#1058965 (PyPy3) No.3068 Speedrun (Hard)

• 問題: No.3068 Speedrun (Hard)
• ユーザー: 👑 SPD_9X2
• 提出日時: 2025-03-24 19:29:36
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 1,969 bytes
• コンパイル時間: 325 ms
• コンパイル使用メモリ: 82,192 KB
• 実行使用メモリ: 67,984 KB
• 最終ジャッジ日時: 2025-03-24 19:29:55
• 合計ジャッジ時間: 16,893 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 6 WA * 7 TLE * 1 -- * 18

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
"""
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:
            continue
        nrem = N - a - b
        
        # (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
        
        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()
        
        
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX