到底是数论不过关。。。

update 15.12.23

Gauss消元

注意自由元和无解的处理

求矩阵逆元

将原矩阵A和一个单位矩阵I做成$(A,I)$，用初等行变换将大矩阵中的A变为E，则会得到$(E,A^{-1})$的形式

Exgcd

解$Ax+By=gcd(A,B)$

在求gcd的基础上加上求x和y

int ex_gcd(int a, int b, int &x, int &y)
{
	if (b==0) 
	{
		x=1, y=0; return a;
	}
	else 
	{
		int d=ex_gcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}
}

单变元模线性方程

解$Ax \equiv B(mod\;p)$

解法：

设$d=gcd(A,p)$，先用Exgcd求$Ax+py=d$的解

如果B不能整除d则无解，否则$mod\;p$意义下的解有d个，可以对某个解不断增加$p/d$得到

多解证明：

$$\frac{Ap}{d=gcd(A,p)}=lcm(A,p) \equiv 0(mod\;p)$$

void line_mod_equation(int a, int b, int n)
{
	int x, y, ans;
	int d=ex_gcd(a,n,x,y);
	if (b%d==0)
	{
		x%=n; x+=n; x%=n; //x mod n
		ans=x*(b/d)%(n/d); //%(n/d)是为了让ans为最小正整数解
		rep(i, 1, d-1)
			ans+=n/d;
	}
}

中国剩余定理

解方程组$x \equiv a_i(mod\;m_i)$，其中$m_i$两两互质

解法：

令$M_i=\prod_{j \neq i}m_j$，解$M_ip_ia_i \equiv a_i(mod\;m_i) \Rightarrow M_ip_i \equiv 1(mod\;m_i)$

每个数解完累加起来，$\sum M_ip_ia_i\;mod\;M$就是答案了

平方剩余

解$x^2 \equiv a(mod\;p)$的最小非负整数解，其中p为素数

无解：当p为2时有解；当p为奇素数时有解的条件：

$$a^{(p-1)/2} \equiv 1(mod\;p)$$

解法：待补充

线性筛

以筛质数为例

void CalPri()
{
	rep(i, 2, n)
	{
		if (valid[i]=false)
			pri[++tot]=i;
		rep(j, 1, tot)
		{
			valid[i]=true;
			if (i%pri[j]==0) break;
		}
	}
}

离散对数（BSGS算法）

解$a^x \equiv b(mod\;p)$的最小整数解，其中p为素数

解法：BSGS算法

设s是满足$s*s>p$的最小整数

先预处理出$x^i(i \in [0,s-1])$并用Hash表储存

然后枚举$x^{is}(i \in [0,s-1])$，通过乘法逆元求出满足$c*x^{is}\equiv n(mod\;p)$的c，再判断c是否位于Hash表内，从而找到解

map<int,int>mp;

inline void GSBS(int a, int b, int p)
{
	mp.clear();
	int s=(int)sqrt(p); while (1LL*s*s<=p) s++;
	int cnt=1; rep(i, 0, s-1) {if (!mp.count(cnt)) mp[cnt]=i; cnt=1LL*cnt*a%p;}
	int mul=cnt, tmp; cnt=1; rep(i, 0, s-1)
	{
		tmp=1LL*b*Pow(cnt,p-2,p)%p;
		if (mp.count(tmp)) {printf("%lld\n", 1LL*i*s+mp[tmp]); return;}
		cnt=1LL*cnt*mul%p;
		if (cnt==0) break;
	}
	puts("Orz, I cannot find x!");
}

Miller_Rabin素数测试

Lucas

求原根

数值积分

高阶代数方程求根

FFT

NTT

这些都待补充。。。