#P5432. A/B Problem(高精度除法)

    ID: 4928 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学倍增O2优化快速傅里叶变换 FFT快速数论变换 NTT

A/B Problem(高精度除法)

题目描述

给你两个正整数 a,ba,b,求 a/b\lfloor a/b \rfloor
为了卡掉一些乱搞做法,你需要对答案进行如下处理:
设答案为 rr,构造一个多项式 F(x)F(x)

$$F(x) = \sum\limits_{i=0}^{\lfloor \lg r \rfloor} (\lfloor 10^{-i}r \rfloor \bmod 10) \cdot x^i $$

简单地说,就是从 rr 的低位到高位,每一位对应 F(x)F(x) 一项的系数。

F(x)F(x) 的最高非零次数为 nn,你需要求出一个 nn 次多项式 G(x)G(x),使得:

F(x)G(x)1(modxn+1)F(x) \cdot G(x) \equiv 1 \pmod{x^{n+1}}

G(x)G(x) 的系数对 998244353998244353 取模,然后升幂输出 G(x)G(x) 的系数即可。

保证满足条件的 G(x)G(x) 存在。

输入格式

两行,每行一个正整数,分别为 aabb

输出格式

输出一行 n+1n+1 个整数,为 G(x)G(x) 的系数

19260817
114514
873463809 93585408 943652865 

提示

【样例解释】

$\left\lfloor \dfrac{19260817}{114514} \right\rfloor = 168$。

由此构造出的多项式 F(x)=x2+6x+8F(x)=x^2+6x+8
求出来对应的 G(x)G(x) 就是 943652865x2+93585408x+873463809943652865x^2 + 93585408x + 873463809

【数据范围】

对于 100%100 \% 的数据,1ba102000001\le b \le a \le 10^{200000}