Tích nhị phân ( Mình hay gọi là binmul (binary multiplication)) là thuật toán tính $a*b$ trong $O(log n)$ , mặc dù trên thực tế phép tính này có thể được thực hiện trong $O(1)$ nhưng trong máy tính chúng ta chỉ lưu chữ được số lớn nhất trong 64bit là đâu đó hơn 10^18 vậy nên nếu ta nhân 2 số trong khoảng hơn $10^9$ với nhau thì rất có thể sẽ tràn số chính vì thế ta phải dùng binmul kết hợp Modulo để tránh tràn số

Code: $O(log n)$

long long MOD = 1e9 + 7;
long long binmul(long long a, long long b)
{
	long long res = 0;
	while(b > 0)
	{
		if(b & 1) res = (res % MOD + a % MOD) % MOD;
		a = (a % MOD + a % MOD) % MOD;
		b /= 2;
	}
	return res % MOD;
}

Ứng dụng

Tránh tràn số

Problem kinh điển

Problem luyện tập