原写作日期：2019-08-24 11:30:21。重置，时间放后 2 年 4 个月。

快速幂

以下以求 $a$ 的 $11$ 次方来介绍。把 $11$ 转换成二进制数 $1011_{(2)}$ 。设其第 $i$ 位的权为 $ 2^{i-1} $。因此，我们将 $a^{11}$ 转化为算 $a^{2^0}+a^{2^1}+a^{2^3}$ 。

ll qpow(ll a,ll p,ll m)
{
    ll r=1;
    while(p)
    {
        r=(p%2?r*a:r)%m;
        p/=2; a=a*a%m;
    }
    return r%m;
}

质数线性筛

check[1]=1;
for(int i=2;i<=n;i++)
{
	if(!check[i]) prime[++cnt]=i;
	for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
	{
		check[i*prime[j]]=1;
		if(i%prime[j]==0) break;
	}
}

中国剩余定理（CRT）

namespace _yz
{
	typedef long long ll;
	const ll N=10+10;
	ll n,a[N],m[N],M=1,Mi,ti,ans=0;
	void exgcd(ll a,ll b,ll &x,ll &y)
	{
		if(b==0)
		{
			x=1; y=0;
			return;
		}
		exgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	ll inv(ll x,ll mod)
	{
		ll y;
		exgcd(x,mod,x,y);
		return (x%mod+mod)%mod;
	}
	void main()
	{
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld",m+i,a+i);
			M*=m[i];
		}
		for(ll i=1;i<=n;i++)
		{
			/*
			  ax=1 (mod b)
			  b|(ax-1)
			  ax-1=by
			  ax-by=1
			  ax'+by'=1
			*/
			Mi=M/m[i]; ti=inv(Mi,m[i]);
			ans=(ans+a[i]*Mi*ti%M)%M;
		}
		printf("%lld\n",ans);
		return;
	}
}

一次同余方程组（ $m_i$ 两两互质），通解：

x=\sum_{i=1}^n a_iM_it_i \pmod M

摘出一项 $i$ 来看（对应 $x\equiv a_i \pmod {m_i}$ ），则 $a_iM_it_i \equiv a_i \pmod{m_i}$ ；而其他各项 $j$ ， $a_jM_jt_j \equiv 0 \pmod{m_i}$ 。

扩展中国剩余定理（EXCRT）

namespace _yz
{
	typedef long long ll;
	const ll N=10+10;
	ll n,a1,b1,a2,b2,d,A1,A2,p1,p2,tmp,x,ans=0;
	ll exgcd(ll a,ll b,ll &x,ll &y)
	{
		ll ret=0;
		if(b==0)
		{
			x=1; y=0;
			return a;
		}
		ret=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return ret;
	}
	ll inv(ll x,ll mod)
	{
		ll y;
		/*  ax=1 (mod b)
		    b|(ax-1)
		    ax-1=by
			ax-by=1
			ax'+by'=1    */
		exgcd(x,mod,x,y);
		return (x%mod+mod)%mod;
	}
	ll mul(ll a,ll b,ll mod)
	{
		ll ret=0;
		if(a>0&&b<0) swap(a,b);
		if(a<0&&b<0) a=-a,b=-b; 
		while(b)
		{
			if(b%2) ret=(ret+a)%mod;
			b/=2; a=(a+a)%mod;
		}
		return (ret%mod+mod)%mod;
	}
	ll lcm(ll a,ll b)
	{
		ll t1,t2;
		return a/exgcd(a,b,t1,t2)*b;
	}
	void main()
	{
		scanf("%lld",&n);
		scanf("%lld%lld",&a1,&b1);
		for(ll i=2;i<=n;i++)
		{
			scanf("%lld%lld",&a2,&b2);
			d=exgcd(a1,a2,A1,A2);
			exgcd(a1/d,a2/d,A1,A2);
			tmp=lcm(a1,a2);
			//x=b1+a1*A1*(b2-b1)/d;
			//x=(b1+((a1*A1%tmp)*(b2-b1)/d)%tmp)%tmp;
			x=mul(b1+mul(a1,mul(A1,(b2-b1)/d,tmp),tmp),1,tmp);
			b1=x; a1=tmp;
		}
		printf("%lld\n",x%a1);
		return;
	}
}
/*
x=b1 (mod a1)
x=b2 (mod a2) 

<1> x=b1+a1*p1
<2> x=b2+a2*p2
<3> a1*p1-a2*p2=b2-b1

a1*p1-a2*p2=b2-b1
p1'=p1, p2'=-p2.

a1*p1'+a2*p2'=b2-b1
(b2-b1)%gcd(a1,a2)!=0,No solution.

Let d=gcd(a1,a2)

<4> a1/d*p1'+a2/d*p2'=1

Let solution of <4> :
 A1=p1', A2=p2'.
 
Solution of:
   a1/d*p1'+a2/d*p2'=(b2-b1)/d
 A1*(b2-b1)/d, A2*(b2-b1)/d.
 
Solution of:
   x=b1 (mod a1)
 b1+a1*A1*(b2-b1)/d

Universal solution of:
   x=b1 (mod a1)
   x=b2 (mod a2)
 b1+a1*A1*(b2-b1)/d+k*lcm(a1,a2)
 
Use tongyu to biaoshi:
   x=b1+a1*A1*(b2-b1)/d (mod lcm(a1,a2))
*/

推导过程见注释。

质因子分解

void factor()
{
	ll n=a,tol;
	for(ll i=2;i<=n;i++)
	{
		if(n%i) continue;
		k[++cnt]=i; tol=0;
		while(n%i==0)
		{
			n/=i; tol++;
		}
		p[cnt]=tol*b;
	}
	if(n>1) {k[++cnt]=n;p[cnt]=b;}
	return;
}

扩展欧几里得算法

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	ll ret=0;
	if(b==0)
	{
		x=1; y=0;
		return a;
	}
	ret=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return ret;
}

获取 $\varphi(n)$ 的值

ll Phi(ll x)//根据欧拉公式
{
	if(phi[x]) return phi[x];
	ll y=x;
	for(ll i=2;i*i<=y;i++)
	{
		if(y%i) continue;
		x=x/i*(i-1);
		while(y%i==0) y/=i;
	}
	if(y!=1) x=x/y*(y-1);
	return x;
}
void AiShi()//埃氏筛
{
	phi[1]=1;
	for(ll i=2;i<n;i++)
	{
		if(phi[i]==0)
		{
			phi[i]=i-1;
			for(ll j=i+i;j<n;j+=i)
			{
				if(phi[j]==0) phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
}
void OLaShai()//欧拉线性筛
{
	phi[1]=1;
	for(ll i=2;i<n;i++)
	{
		if(phi[i]==0)
		{
			phi[i]=i-1;
			prime[++cnt]=i;
		}
		for(ll j=1;j<=cnt&&i*prime[j]<n;j++)
		{
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}