数论模板

#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)

欧几里德算法（辗转相除法）

（1）可以用来求最大公约数和最小公倍数

（2）注意题目的数据是否在int内，中间结果有溢出的可能，根据情况开long long

（3）记得最大公倍数是先除后乘，防止溢出

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

拓展欧几里得算法（求 ax + by = gcd（a， b）的一组解）

（１）求出一组解（x0， y0）后，可求出其他所有解

x = x０ +ｋ＊（ｂ／ｇｃｄ（ａ，ｂ））　

y = ｙ０－ｋ＊（ａ／ｇｃｄ（ａ，ｂ））　

其中ｋ为任意整数

（２）若求ａｘ＋by = c的整数解

如果c 不是ｇｃｄ（ａ，ｂ）的倍数，则方程无整数解

如果是，那么两边同时乘以 c / ｇｃｄ（ａ，ｂ）即为解

即（x0 *c / ｇｃｄ（ａ，ｂ）， y0 * c / ｇｃｄ（ａ，ｂ））

void exgcd(int a, int b, int& d, int& x, int& y)
{
	if(!b) { d = a; x = 1; y = 0; }
	else { exgcd(b, a % b, d, y, x); y -= x * (a / b) ; } //y -= x * (a / b) 要记忆 
}

素数筛

nlogn筛法

const int MAXN = 11234567;
bool is_prime[MAXN];
int n, m;

void get_prime() // n以内的素数
{
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	int m = sqrt(n + 0.5);
	_for(i, 2, m)
	   if(is_prime[i])
	      for(int j = i * i; j <= n; j += i)
	         is_prime[j] = false;
}

线性筛法

const int MAXN = 11234567;
bool is_prime[MAXN];
vector<int> prime;

void get_prime() 
{
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	REP(i, 2, MAXN)
	{
		if(is_prime[i]) prime.push_back(i);
		REP(j, 0, prime.size())
		{
			if(i * prime[j] >= MAXN) break; //注意这里是大于等于不是大于
			is_prime[i * prime[j]] = false;
			if(i % prime[j] == 0) break;
		}
	}
}

快速幂（求a的b次方模n）

ll cal(ll a, ll b, ll p)
{
	ll ret = 1 % p; a %= p; //保险起见
	while(b)
	{
		if(b & 1) ret = ret * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return ret;
}

64位整数乘法

typedef long long ll;
ll pow(ll a, ll b, ll p)
{
	ll res = 0; a %= p; //res = 1 % p 改成 res = 0 
	for(; b; b >>= 1)
	{
		if(b & 1) res = (res + a) % p; //乘a改成加a 
		a = a * 2 % p; //a * a 改成 a * 2 
	}
	return res; 
}

唯一分解定理

void add_integer(int n, int d) //表示把n的d次方质因数分解，结果存到数组e里面 
{							  //例如d = 1表示乘以n，d = -1表示除以n 
	REP(i, 0, prime.size()) //需要预处理好素数 
	{
		while(n % prime[i] == 0) //注意这里是while 
		{
			n /= prime[i];
			e[i] += d; //e[i]表示第i个素数的幂
		}
		if(n == 1) break; //节省时间 
	}
}

杨辉三角与二项式定理

第n行第k列的系数为c（n, k）

注意行和列都是从0开始

满足递推式c(n, k) = c(n,k-1)*(n-k+1)/k

所有系数

void init()
{
	REP(i, 0, MAXN)
	{
		c[i][0] = 1;
		_for(j, 1, i)
			c[i][j] = c[i-1][j] + c[i-1][j-1];		
	}
}

第n行系数

//注意先乘后除，因为先除不一定可以整除
//注意中间结果可能溢出要用long long 
c[0] = 1; 
REP(i, 1, n + 1) c[i] = c[i-1] * (n-i+1) / i;

欧拉函数（求1到N与N互质的数的个数）

单独求一个数的欧拉函数

int euler(int n)
{
	int ret = n;
	for(int i = 2; i * i <= n; i++)
		if(n % i == 0)
		{
			ret = ret / i * (i - 1);
			while(n % i == 0) n /= i;
		}
	if(n > 1) ret = ret / n * (n - 1);
	return ret;
}

1~n所有数欧拉函数的值

void get_euler(int n)
{
	_for(i, 1, n) euler[i] = i;
	_for(i, 2, n + 1)
		if(euler[i] == i)
			for(int j = i; j <= n; j += i)
				euler[j] = euler[j] / i * (i - 1);
}

Catalan数

h(0) = 0, h(1)=1, h(n) = h(n-1) * (4*n-2) / (n+1);

f[1] = 1;
REP(i, 2, MAXN) 
	f[i] = f[i-1] * (4 * i - 2) / (i + 1);

组合数

void init()
{
	REP(i, 0, MAXN)
	{
		c[i][0] = 1;
		_for(j, 1, i)
			c[i][j] = c[i-1][j] + c[i-1][j-1];		
	}
}

线性求1~p的逆元（mod p）

void get_inv()
{
	inv[1] = 1;
	REP(i, 2, MAXN)
		inv[i] = (p - p / i) * inv[p % i] % p;
}

高次同余方程（BSGS算法）

模板题

#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
ll a, b, p;

ll power(ll a, ll b, ll p)
{
	ll res = 1 % p; a %= p;
	for(; b; b >>= 1)
	{
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

inline ll inv(ll a) { return power(a, p - 2, p); }

map<ll, ll> mp;
void BSGS()
{
	a %= p; b %= p;
	if(a == 0 && b == 0) { puts("1"); return; }
	if(a == 0 && b != 0) { puts("no solution!"); return; }
	
	ll m = ceil(sqrt(p));
	mp.clear();
	mp[b] = m + 1;
	ll sum = 1, t = inv(a);
	REP(j, 1, m)
	{
		sum = sum * t % p;
		ll q = b * sum % p;
		if(!mp[q]) mp[q] = j;
	}
	
	sum = 1; t = power(a, m, p);
	REP(i, 0, m)
	{
		if(mp[sum])
		{
			if(mp[sum] == m + 1) printf("%lld
", i * m);
			else printf("%lld
", i * m + mp[sum]);
			return;
		} 
		sum = sum * t % p;
	} 
	puts("no solution!");
}

int main()
{
	while(~scanf("%lld%lld%lld", &p, &a, &b)) BSGS();
	return 0;
}

Lucas定理求大组合数

ll power(ll a, ll b)
{
	ll res = 1 % p; a %= p;
	for(; b; b >>= 1)
	{
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

inline ll inv(ll a) { return power(a, p - 2); }

ll C(ll n, ll m)
{
	if(m > n) return 0;
	ll a = 1, b = 1;
	_for(i, n - m + 1, n) a = a * i % p;
	_for(i, 1, m) b = b * i % p;
	return a * inv(b) % p;
}

ll Lucas(ll n, ll m)
{
	if(!m) return 1;
	return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

中国剩余定理

ll M = 1;
REP(i, 0, n)
{
	scanf("%lld%lld", &m[i], &a[i]);
	M *= m[i];
}
	
ll ans = 0, d, x, y;
REP(i, 0, n)
{
	ll mi = M / m[i];
	exgcd(mi, m[i], d, x, y);
	ans = (ans + x * mi * a[i]) % M;
} 
ans = (ans % M + M) % M;
printf("%lld
", ans);