求助
查看原帖
求助
747009
Spir1t楼主2023/10/7 20:30

rt,样例过了

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_gcd(b, a % b)
        return gcd, y, x - (a // b) * y

def inverse_modulo(n, mod):
    _, inv, _ = extended_gcd(n, mod)
    return inv % mod

def polynomial_inverse(f, n, mod):
    g = [0] * n  # 初始化 G(x) 的系数为 0
    g[0] = inverse_modulo(f[0], mod)  # 计算 G(x) 的常数项系数
    for i in range(1, n):  # 从次低位开始计算 G(x) 的系数
        coeff = 0
        for j in range(i, -1, -1):
            coeff += (f[j] * g[i-j]) % mod
        g[i] = (-coeff * inverse_modulo(f[0], mod)) % mod
    return g

def ab_division(a, b, mod):
    quotient = a // b  # 计算商
    f = []  # 多项式 F(x) 的系数
    while quotient > 0:
        f.append(quotient % 10)
        quotient //= 10
    n = len(f) - 1  # F(x) 的最高非零次数
    g = polynomial_inverse(f, n+1, mod)  # 计算 G(x) 的系数
    return g


a = int(input())
b = int(input())


mod = 998244353


result = ab_division(a, b, mod)


print(*result)
2023/10/7 20:30
加载中...