模板代码大全（持续更新ing...）

数论

快速幂

求 $x^y\mathrm{mod}p$。

long long power(long long x,int y){
	long long res=1;
	for(;y;y>>=1){
		if(y&1)res=res*x%p;
		x=x*x%p;
	}
	return res;
}

Lucas 定理

求 $C_n^m\mathrm{mod}p$

long long fac[p],inv[P];
// 此处省略快速幂 power 函数
void init(){
	fac[0]=inv[0]=1;
	for(int i=1;i<P;++i)fac[i]=fac[i-1]*i%p,inv[i]=power(fac[i],p-2);
}
long long C(int n,int m,int p){
    if(m>n)return 0;
    return fac[n]*inv[n-m]%p*inv[m]%p;
}
long long Lucas(int n,int m,int p){
	if(m==0)return 1;
	return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

素数筛法

Eratosthenes 筛法

bool st[N];
int primes[N],tot=0;
void Eratosthenes(int n){
	for(int i=2;i<=n;++i){
		if(st[i])continue;
		primes[++tot]=i;
		for(int j=i;j<=n/i;++j)st[i*j]=true;
	}
}

Euler 筛法（线性筛法）

int st[N],primes[N],tot=0;
void Euler(int n){
	for(int i=2;i<=n;++i){
		if(!st[i])primes[++tot]=st[i]=i;
		for(int j=1;j<=tot;++j){
			if(primes[j]>st[i]||primes[j]>n/i)break;
			st[i*primes[j]]=primes[j];
		}
	}
}

质因数分解

分解 $n$ 的质因数，从小到大依次输出。

for(int i=2;i<=n/i;++i)
	while(n%i==0)cout<<i<<' ',n/=i;
if(n!=1)cout<<n<<' ';

求某个数的正约数集合

从小到大输出 $n$ 的所有约数。

vector<int>s,t;
for(int i=1;i<=n/i;++i)
	if(n%i==0){
		s.push_back(i);
		if(i!=n/i)t.push_back(n/i);
	}
for(int i=0;i<s.size();++i)cout<<s[i]<<' ';
for(int i=t.size()-1;i>=0;--i)cout<<t[i]<<' ';

最大公约数

求 $x$ 和 $y$ 的最大公约数。

int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}

最小公倍数

求 $x$ 和 $y$ 的最小公倍数。

//此处省略最大公约数 gcd 函数
long long lcm(int x,int y){
	return(long long)x*y/gcd(x,y);
}

欧拉函数

求 $\phi (n)$。

int phi(int n){
	int ans=n;
	for(int i=2;i<=n/i;++i){
		int c=0;
		while(n%i==0)n/=i,c++;
		if(c)ans=ans/i*(i-1);
	}
	if(n!=1)ans=ans/n*(n-1);
	return ans;
}

函数筛法

筛欧拉函数

int st[N],primes[N],phi[N],tot=0;
void getPhi(int n){
	for(int i=2;i<=n;++i){
		if(!st[i])primes[++tot]=st[i]=i,phi[i]=i-1;
		for(int j=1;j<=tot;++j){
			if(primes[j]>st[i]||primes[j]>n/i)break;
			st[i*primes[j]]=primes[j];
			if(i%primes[j]==0)phi[i*primes[j]]=phi[i]*primes[j];
			else phi[i*primes[j]]=phi[i]*(primes[j]-1);
		}
	}
}

筛莫比乌斯函数

int st[N],primes[N],mu[N],tot=0;
void getPhi(int n){
	for(int i=2;i<=n;++i){
		if(!st[i])primes[++tot]=st[i]=i,mu[i]=-1;
		for(int j=1;j<=tot;++j){
			if(primes[j]>st[i]||primes[j]>n/i)break;
			st[i*primes[j]]=primes[j];
			if(i%primes[j]==0)mu[i*primes[j]]=0;
			else mu[i*primes[j]]=-mu[i];
		}
	}
}