Introduction to number theory (greatest common divisor, prime sieve, inverse element)

One 、 greatest common divisor （gcd）

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

gcd（a,b,c）=gcd（a,b-a,c-b） Most of them can be promoted

Two 、 Prime sieve （ Euler screen , For Euler function ）

int least[maxn], prime[maxn], phi[maxn], tot;
void euler(int n)
{
	int i, j;
	for (i = 2; i <= n; i++)
	{
		if (!least[i])
		{
			least[i] = i;
			prime[++tot] = i;
			phi[i] = i - 1;
		}
		for (j = 1; j <= tot && i * prime[j] <= n; j++)
		{
			least[i * prime[j]] = prime[j];
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else
			{
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			}
		}
	}
}

3、 ... and 、 Fast power inverse （ Used for finding large combinatorial numbers ）

// Calculate large numbers （a/b）mod c
ll quick_pow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}
ll inv(ll a, ll b)
{
	return (a * quick_pow(b, mod - 2)) % mod;
}

ll fa[maxn], fb[maxn];
ll power(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll C(ll n, ll k)
{
	if (k<0 || k>n)
		return 0;
	return fa[n] * fb[k] % mod * fb[n - k] % mod;
}
void init()
{
	int i;
	fa[0] = 1;
	fb[0] = 1;
	for (i = 1; i < maxn; i++)
	{
		fa[i] = fa[i - 1] * i % mod;
		fb[i] = power(fa[i], mod - 2) % mod;
	}
}