Hello Codeforces!

Today I'll write down what I learn about combinatorics, and I think it common in Codeforces contests and competitive programming.

However, combinatorics is a great subject, and I cannot write it all in one blog. So, this is just the first blog, it's for beginners. If you are interested, please, pay attention to this account and it'll give posts like this for a long term.

If there is something wrong in the text, or if you have some problems about the topic, just give a comment, I'll check it weekly and reply. Also, if you find some grammar mistakes, welcome too.

Content

1. Quick power
2. Fermat's little theorem
3. extent-gcd
4. The multiplicative inverse of an integer
5. Prework optimize
6. homework

Part 1 — Quick power

How to calculate the value of $$$a^b\bmod p$$$?

You may write out this code easily:

long long power(long long a, long long b, long long p) {
	long long res = 1;
	while(b--) res = res * a % p;
	return res;
}

Seems easy, right? This code has $$$\mathcal O(b)$$$ time complexity. But what if $$$1\leq a,b\leq 10^9$$$? Can you solve it?

Here, we use divide ans conquer to solve this:

According to this, we can write out a code easily:

long long powpow(long long a, long long b, long long p) {
	if(b % 2 == 1) {
		long long r = powpow(a, b / 2, p);
		return r * r % p * a % p;
	} else {
		long long r = powpow(a, b / 2, p);
		return r * r % p;
	}
}

Now certainly the time complexity is $$$\mathcal O(\log b)$$$. But this code contains a recursion. Since the recursion is simple, we can get rid of recursion:

long long quickpow(long long a, long long b, long long p) {
	long long res = 1, nowa = 1;
	while(b) {
		if(b % 2 == 1) res = res * nowa % p;
		nowa = a * a % p;
		a = nowa;
		b /= 2;
	}
	return res;
}

Now I'll give a fast version of it without explaining, you can use it in the later implementaions.

long long quickpow(long long a, long long b, long long p) {
	long long res = 1;
	while(b) {
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

The time complexity remains the same, but the constant is smaller now. If you still wonders why, you can wait for my bitmask post.