A/B Problem(高精度除法)
题目描述
给你两个正整数 $a,b$,求 $\lfloor a/b \rfloor$。
为了卡掉一些乱搞做法,你需要对答案进行如下处理:
设答案为 $r$,构造一个多项式 $F(x)$:
$$ F(x) = \sum\limits_{i=0}^{\lfloor \lg r \rfloor} (\lfloor 10^{-i}r \rfloor \bmod 10) \cdot x^i$$
简单地说,就是从 $r$ 的低位到高位,每一位对应 $F(x)$ 一项的系数。
设 $F(x)$ 的最高非零次数为 $n$,你需要求出一个 $n$ 次多项式 $G(x)$,使得:
$$ F(x) \cdot G(x) \equiv 1 \pmod{x^{n+1}}$$
将 $G(x)$ 的系数对 $998244353$ 取模,然后升幂输出 $G(x)$ 的系数即可。
保证满足条件的 $G(x)$ 存在。
输入输出格式
输入格式
两行,每行一个正整数,分别为 $a$ 和 $b$。
输出格式
输出一行 $n+1$ 个整数,为 $G(x)$ 的系数
输入输出样例
输入样例 #1
19260817
114514
输出样例 #1
873463809 93585408 943652865
说明
**【样例解释】**
$\left\lfloor \dfrac{19260817}{114514} \right\rfloor = 168$。
由此构造出的多项式 $F(x)=x^2+6x+8$
求出来对应的 $G(x)$ 就是 $943652865x^2 + 93585408x + 873463809$。
**【数据范围】**
对于 $100 \%$ 的数据,$1\le b \le a \le 10^{200000}$。