本原勾股数

每个本原勾股数组$(a,b,c)$（其中a为奇数b为偶数）都满足

$$a=st \quad b=\frac {s^2-t^2}{2} \quad c=\frac {s^2+t^2}{2} \quad (s > t \ge 1 \; and \; gcd(s,t)=1 \; and \; s,t为奇数)$$

恒等式

$$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$$

线性筛

以筛质数为例

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;
		}
	}
}

Miller–Rabin素数测试

测试$N$是否为素数，记$2^s d=N-1$

对$a \in [1,N-1]$且$a \nmid n$

若$a^d \mod N \neq 1$且$a^{2^{r}d} \mod N \neq -1 \quad (r \in [0, s-1])$

则N是合数

否则，N有3/4的概率为素数

inline ll Mult(ll x, ll t, ll Q)
{
	ll k=0; while (t)
	{
		if (t&1)
		{
			k+=x; if (k>=Q) k-=Q;
		}
		t>>=1; x+=x; if (x>=Q) x-=Q;
	} return k;
}
inline ll Pow(ll x, ll t, ll Q)
{
	ll k=1; while (t)
	{
		if (t&1) k=Mult(k,x,Q);
		t>>=1; x=Mult(x,x,Q);
	} return k;
}

inline bool MR(ll n) // Miller_Rabin
{
	if (n<2) return false;
	if (n==2) return true;
	if ((n&1)==0) return false;
	ll d=n-1, s=0;
	while ((d&1)==0) d>>=1, s++;
	rep(tm, 1, 8)
	{
		ll a=rand()%(n-1)+1, ret=Pow(a,d,n), last=ret;
		rep(i, 1, s)
		{
			ret=Mult(ret,ret,n);
			if (ret==1 && last!=1 && last!=n-1) return false;
			last=ret;
		}
		if (ret!=1) return false;
	}
	return true;
}

Pollard_rho质因素分解

ll gcd(ll a, ll b){return b==0?a:gcd(b,a%b);}
inline ll PR(ll n, ll c)  // Pollard_rho
{
	int i=0, k=1; ll x=rand()%n, y=x;
	while (1)
	{
		i++;
		x=(Mult(x,x,n)+c)%n;
		ll d=gcd(y>x?y-x:x-y,n);
		if (d!=1 && d!=n) return d;
		if (y==x) return n;
		if (i==k) y=x, k<<=1, i=0;
	}
}

ll q[109]; int tot;
void FindFac(ll n)
{
	if (MR(n)) {q[++tot]=n; return;}
	ll p=n; while (p==n) p=PR(p,rand()%(n-1)+1);
	FindFac(p); FindFac(n/p);
}

费马大定理

当$n \ge 3$时方程

$$a^n+b^n=c^n$$

没有正整数解

费马小定理

$$\quad a^{p-1} \equiv  1 \pmod{p}$$

变式：（前提$gcd(a,n)=1$）

$$a^{\varphi(n)} \equiv 1 \pmod n \quad（欧拉定理）$$

威尔逊定理

$$(p-1)! \equiv -1 \pmod p$$

乘法逆元

①数$a$在$\pmod p$意义下的逆元为$a^{p-2}$

②数$a$在$\pmod n$意义下的逆元需要通过Exgcd求解（有可能不存在逆元）

中国剩余定理（CRT）

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

解法：

令

$$M_i=\prod_{j \not = i}m_j$$

解

$$M_ip_ia_i \equiv a_i \quad \Rightarrow \quad M_ip_i \equiv 1\pmod{m_i}$$

所有$p_i$解完累加起来，$\sum M_ip_ia_i \pmod{M}$就是答案了

欧几里德算法

int gcd(int a, int b){return b==0?a:gcd(b,a%b);}

扩展欧几里德算法

解线性方程$Ax+By=gcd(A,B)$

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

原理：$By+(A\;mod\;B)x \Rightarrow B(y-A/B*B*x/B)+Ax \Rightarrow Ax+B(y-A/B*x)$

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 \pmod 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 \pmod 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;
	}
}

Gray码

性质：一个$0\rightarrow2^n-1$的排列且相邻两项（包括头尾相邻）的二进制数中只有一位不同

高阶代数方程求根

数值积分

AKS素数测试