---
tags: codebook
---

# mul

## mathematical $O(1)$

inline unsigned long long mul(unsigned long long a , unsigned long long b, unsigned long long m) {
	long long r = a * b - (long long)((long double)a / m * b + 0.5) * m;
	return r < 0 ? r + m : r;
//	return a * b % m;
}

## divided $O(logn)$

inline unsigned long long mod(unsigned long long a, unsigned long long m) {
	size_t n = __builtin_clzll(m);
	for (m <<= n++; n--; m >>= 1)
		if (a >= m) a -= m;
	return a;
//	return a % m;
}
inline unsigned long long comparison_based_mod(unsigned long long a, unsigned long long m) {
	return a >= m ? a - m : a;
}
inline unsigned long long mul(unsigned long long a , unsigned long long b, unsigned long long m) {
	unsigned long long res = 0;
	for (a = mod(a, m); b; b >>= 1, a = comparison_based_mod(a << 1, m))
		if (b & 1) res = comparison_based_mod(res + a, m);
	return res;
//	return a * b % m;
}

## pow O(logn)

inline unsigned long long pow(unsigned long long a, unsigned long long b, unsigned long long m) {
	unsigned long long res = 1;
	for (a = mod(a, m); b; b >>= 1, a = mul(a, a, m))
		if (b & 1) res = mul(res, a, m);
	return res;
}