結果

問題 No.3278 Avoid Division
ユーザー 👑 loop0919
提出日時 2025-09-19 23:28:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 2,599 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 57,304 KB
最終ジャッジ日時 2025-09-19 23:28:58
合計ジャッジ時間 4,484 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

from random import randint


def miller_rabin(n: int):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    n1 = n - 1
    d = n1
    s = 0
    while (d & 1) == 0:
        d //= 2
        s += 1

    for a in (2, 325, 9375, 28178, 450775, 9780504, 1795265022):
        if a % n == 0:
            continue
        t = pow(a, d, n)  # = pow(a, d) % n
        if t == 1 or t == n1:
            continue
        for _ in range(s - 1):
            t = pow(t, 2, n)  # = pow(t, 2) % n
            if t == n1:
                break
        else:
            return False
    return True


def randprime(start, end):
    """ランダムな素数を生成する（注意: [start, end) 内に素数がないと無限ループになる）"""
    s, e = start >> 1, (end - 1) >> 1
    while True:
        rand = randint(s, e) * 2 + 1
        if miller_rabin(rand):
            return rand


class Var:
    def __init__(self, val, idx):
        self.idx = idx
        self.val = val

    def __str__(self):
        return chr(self.idx + ord("a"))


class ArrayVal:
    def __init__(self, val, idx):
        self.idx = idx
        self.val = val

    def __str__(self):
        return f"A[{self.idx + 1}]"


Value = Var | ArrayVal

P = randprime(10**9, 2 * 10**9)
N = int(input())
variables = [Var(0, i) for i in range(26)]

answer = []


def add(x: Var, y: Value, z: Value):
    global variables
    variables[x.idx] = Var((y.val + z.val) % P, x.idx)
    answer.append(f"add {x} {y} {z}")


def mul(x: Var, y: Value, z: Value):
    global variables
    variables[x.idx] = Var((y.val * z.val) % P, x.idx)
    answer.append(f"mul {x} {y} {z}")


def div(x: Var, y: Value, z: Value):
    global variables
    variables[x.idx] = Var(y.val * pow(z.val, P - 2, P) % P, x.idx)
    answer.append(f"div {x} {y} {z}")


commands, A = [], []

for i in range(N):
    cmd, a = input().split()
    a = int(a)

    commands.append(cmd)
    A.append(ArrayVal(a, i))


for i in range(N):
    cmd = commands[i]
    a = A[i]

    if cmd == "+":
        if variables[1].val == 0:
            add(variables[0], variables[0], a)
        else:
            mul(variables[-1], variables[1], a)
            add(variables[0], variables[0], variables[-1])
    elif cmd == "*":
        mul(variables[0], variables[0], a)
    elif cmd == "/":
        if variables[1].val == 0:
            add(variables[1], variables[1], a)
        else:
            mul(variables[1], variables[1], a)

if variables[1].val != 0:
    div(variables[0], variables[0], variables[1])

print(len(answer))
print(*answer, sep="\n")
0