晶石齁入(77tps可入，如果还没做最好先做再看)

一定要提前思考一下在极端条件下乘法是否会爆掉假如都为10^10,那么最大为10^20。就算你这么写

CPP

int fastpow(int x,int y)
{
	int ans=1;
	while (y)
	{
		if (y%2) ans=(ans%mod*x%mod)%mod;
		x=(x%mod*x%mod)%mod;
		y/=2;
	}
	return ans%mod;
}

由于mod最大为10^10+1,这个取模可能无效。

所以还是得写一个快速乘函数避免过大，而其原理和快速幂差不多，由于a*b实际上就是b个a相加，那么我们就可以再根据(a+b)%mod等效于(a%mod+b%mod)%mod的性质来进行一些处理，实际上很好理解代码如下：

CPP

int mul(int a,int b)
{
	int ans=0;
	while (b)
	{
		if (b%2) ans=(ans+a)%mod;
		a=(a+a)%mod;
		b/=2;
	}
	return ans%mod;
}

这样在计算exgcd的时候就可以把乘法直接改成mul函数，不会担心爆掉，而本蒟蒻在讨论版和题解中逛了一大圈才幡然醒悟，OTZ

~~第一次A掉是觉得自己对了以为题解错了，把题解交上去，结果一看我是乐子~~

讨论操作