[TJOI2009]猜数字
本题所需算法：
中国剩余定理—-模板
龟速乘
以下部分主要为扩展中国剩余定理的推导过程(与本题无关，不想看的可以直接跳过)
首先我们要知道中国剩余定理的使用要求
即题目要求中可以化为一下方程组
$$
\begin{cases}
x\equiv b_1(mod(a_1)) \\
x\equiv b_2(mod(a_2)) \\
x\equiv b_3(mod(a_3)) \\
\cdots\cdots\cdots \\
x\equiv b_n(mod(a_n))
\end{cases}
$$
对于每对方程，我们可以得到
$$
\begin{cases}
x=b_a + k_a\cdot a_a \\
x=b_b + k_b\cdot a_b
\end{cases}
$$
联立化简一下
$$
k_a\cdot a_a + k_b\cdot a_b = b_b - b_a
$$
对于这个式子，我们可以用 $exgcd$ 求出 满足要求的关于 $x$ 特解 $x_0$ ,那么可以得到以下式子
$$
\begin{cases}
x_0=b_a + k_a\cdot a_a \\
x=b_a + k_i\cdot a_a \\
k_i=n\cdot\frac{a_b}{\gcd(a_a,a_b)} + k_a(n\in Z)
\end{cases}
$$
那么可以得到
$$
x=n\cdot\frac{a_b\cdot a_a}{\gcd(a_a,a_b)} + k_a\cdot a_a + b_a = n\cdot lcm(a_a,b_a) + x_0(n\in Z)
$$
最后两个同余式就可以合并为
$$
x\equiv x_0\mod lcm(a_a,a_b)
$$
回到中国剩余定理，
由于模数 $P_i$ 都为质数，我们可以设
$n_i$是满足下面两个式子的最小正整数
$$
\begin{cases}
n_i\equiv b_i \mod a_i\\
\frac{\prod_{j=1}^{k}{a_j}}{a_i}\mid n_i
\end{cases}
$$
那么 $\sum_{i=1}^k{n_i}$ 一定是满足条件一个解。
但是这并不是满足条件的最小值，所以我们还要在此基础上对 $\prod_{j=1}^{k}{a_j}$ 取模
那么怎么计算 $n_i$ 呢？
我们可以运用 $exgcd$ 求出满足
$n_i\equiv 1(mod(a_i))$ 的 $n_i$ ,那么可以得出
$$
b_i\cdot n_i\equiv b_i \mod a_i
$$
所以我们答案为
$$
\begin{cases}
ans=\sum_{i=1}^k{n_i\cdot b_i}\\
n_i\equiv 1\mod a_i
\end{cases}
$$
代码实现
inline ll china()
{
ll W=1,k,z,w,ans=0;
for(int i=1;i<=n;++i)W*=a[i];
for(int i=1;i<=n;++i)
{
w=W/a[i];
exgcd(w,a[i],k,z);
ans=(ans+slow(slow(w,k,W),b[i],W))%W;
}
return ans=(ans+W)%W;
}龟速乘
将乘法进行二进制拆分，分步取模防止单次乘法溢出,代码类似于快速幂，只需要将其中的乘法换成加法
代码实现
inline ll slow(ll a,ll b,ll mod)
{
ll ans=0;
if(b<0)b=(b%mod+mod)%mod;\\如果 b 为负数，龟速乘可能会炸掉，所以先取模将b改为正整数
while(b)
{
if(b%2)ans=(ans+a)%mod;
b=b>>1;
a=(a<<1)%mod;
}
return ans;
}$$
\large\color{grey}{\text{Thanks for your reading}}
$$
