诈骗题*1

有些说法不是很严谨，毕竟是给有数学基础而对 OI 不熟悉的人讲随机模数 CRT 和其他的一些东西的，所以喷的话留情 qwq

已知 $a,b,c$ 三数， $a,b,c\leq 10^N$ ，其中 $N\leq 5\times 10^6$

多组输入，数据组数 $T\leq 20$

你需要判断 $a\times b$ 是否等于 $c$

讲个笑话，原来的题面是这样的：

给一个 $seed$ ，用下发的随机数据生成器生成 $a,b,c$ 三数， $a,b,c\leq 10^N$ ，其中 $N\leq 10^7$

多组输入，数据组数 $T\leq 50$

你需要判断 $a\times b$ 是否等于 $c$

这个更苛刻，把三个数搞出来常数大点就挂了（

就是开一个数组，每一位塞到数组的一个数中，拿小学的列竖式的方法算

压位高精是指把数组省着用，但思路不变

为啥会挂？会小学数学列竖式的都知道，每一位都要操作，那就是操作 $2.5\times 10^{13}$ 次，比对 $5\times 10^6$ 次操作，算起来就是 $5\times10^{14}$ 次操作至少

过了 $10^8$ 次操作就会挂，即使存的下，也跑不动（

众所周知 Python 慢得离谱，读入就超时了，哈哈

Ruby 差不多吧，肯定能卡掉（已经卡掉了）

FFT（Fast Fourier Transform），快速傅里叶变换

不会多项式/kk

你 $\Theta(n\log n)$ 的肯定太慢了过不了啊

补充： $\Theta()$ 是什么鬼

比如做法 1， $a$ 的每一位都要和 $b$ 乘，操作 $n^2$ 次，那么时间复杂度就是 $\Theta(n^2)$

时间复杂度是啥？这个百度百科吧，不过不是很重要（

CRT，中国剩余定理（不会的补小学奥数去）

其中有个细节

\begin{cases} a\equiv b_1\pmod {p_1}\\ a\equiv b_2\pmod {p_2}\\ a\equiv b_3\pmod {p_3}\\ ·\\ ·\\ ·\\ a\equiv b_m\pmod {p_m}\\ \end{cases}

可以构造出多个 $a$ 满足要求

但是如果 $a$ 足够大，除了最小的以外，其他的都大于最大边界，那就非常 OK 了

而且模数有个性质， $a\equiv a_1\pmod {p},b\equiv b_1\pmod {p}\Rightarrow a\times b\equiv a_1\times b_1\pmod {p}$

所以就可以选几个 $p$ ，然后如果 $(a\bmod p\times b \bmod p)\bmod p=c\bmod p$ ，就可以认为是正确的了

$p$ 得随机选，否则就能用 CRT 构造出反例，gg

当然 $p$ 的个数和大小得慎重考虑，否则会时间不够或成功率低，这个要平衡

这个挺快的，如果容许犯错的话。可以开到原题面那么多，然后卡卡常搞搞，极限卡过没问题应该