板子

欧拉函数：

1
2
3
4
5
6
7
8
9
10
void pir(int a){
	int res = a;
	for(int i = 2;i <= a / i;++i)
		if(a % i == 0){
			res = res / i *(i - 1);
			while(a % i == 0)a /= i;
		}
	if(a > 1)res = res / a * (a - 1);
	cout<<res<<endl;
}

最大公约数（gcd）：

1
2
3
int gcd(int a,int b){
	return b ? gcd(b, a % b) : a; 
}

最小公约数（lcm）：

1
2
3
int lcm(int a,int b){
	return a * b / gcd(a, b);
}

埃氏筛：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool b[5000001];//标记范围内所有数 
long long prim[5000000];//存素数 
int ai(int n){
	int p = 0;//素数个数 
	for(int i = 0;i <= n;i++)b[i] = true;//所有数先标记为真 
	b[0] = b[1] = false;//0，1标记为素数 
	for(int i = 2;i <= n;i++){
		if(b[i]){
			prim[p++] = i;
			for(int j = i * i;j <= n;j += i)b[i] = false;
		}
	} 
	return p;
}

欧拉筛：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool a[50000];
a[1]=1;//注意1不是质数；
int p[50000],t;
for(int i=2;i<=n;i++)
{
	if( a[i] == 0 )
		p[++t]=i;//是质数就记录；
	for(int j=1;j<=t && i*p[j]<=n;j++)
	{
		a[ i*p[j] ]=1;//标记合数；
		if( i%p[j] == 0 )
			break;
		//保证同一个合数不会被多个质数标记。
	}
}

素数判断：

1
2
3
4
5
bool check(int n){
	for(int i = 2;i * i <= n;i++)
		if(i % n ==0)return false;
		else return true;
}

快速乘：

1
2
3
4
5
6
7
typedef long long ll;
inline ll mul(ll x,ll y,ll p){
	register ll res = 0;
	for(; y; y >>= 1,x = (x + x) % p)
	if(y & 1)res = (res + x) % p;
	return res;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
long long B,P,K;
//没用二进制优化
long long qpow(int base,int p){
	if(p==1) return base;//幂数为1时，直接返回原数
	else if(p==0) return 1;//幂数为0时，dddd 
	else{
		long long ans = qpow(base,p / 2) % K;//以递归的方法将O(n)的复杂度优化到O(log2n) 
		long long ans1 = (ans % K * ans % K) % K;
		if(p % 2 == 1)ans1 = (ans1 % K * base % K) % K;
		ans1 = ans1 % K;
		return ans1;
	}
}

快速幂（二进制优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll n,m,k;//n:底数，m:模数，k:幂数 
ll qp(int x,int y){
	ll a = 1,b = x;
	while(y > 0){
		if(y % 2 == 1){
			a = a * b;
			a = a % m;
		}
		b = b * b;
		b = b % m;
		y = y / 2;
	}
	return a;
}

快速幂（递推）

1
2
3
4
do{     //递推快速幂，与普通的递推快速幂无异，但*不能缩写为*=
		if(k&1)ans=ans*a;
		a=a*a;k>>=1;
	}while(k);

勒让德定理

1
2
3
4
5
6
7
8
int lrd(int sum,int n,int k){
	int t = n / k;
	if(t != 0){
		k *= k;
		sum = lrd(sum + t, n, k);
	}
	return sum;
}

扩展欧几里得

1
2
3
4
5
6
7
8
int exgcd(int a,int b,int &x,int &y){
	if(b == 0)x = 1,y = 0,return a;
	int d = exgcd(b, a % b, x, y);
	int t = y;
	y = x - a / b * t;
	x = t;
	return d;
}