ll mul(ll a,ll b,ll p) { if(a>1e9||b>1e9){ ll x = 1LL<<25; ll L = a * (b >> 25LL) % p * x % p; ll R = a * (b & (x - 1)) % p; return (L + R) % p; } else return a*b%p; }
运用乘法分配率，将b分成大于$2^{25}$的部分与小于$2^{25}$的部分乘。
原文：https://www.cnblogs.com/MYsBlogs/p/10822201.html