大数相乘取模

https://www.cnblogs.com/shuaihui520/p/9619322.html

记一下

a∗bmodp=a∗b−⌊a∗bp⌋∗pa∗bmodp=a∗b−⌊a∗bp⌋∗p
用long double来计算⌊a∗bp⌋⌊a∗bp⌋,误差很小，因为long double的特性是存不下就舍弃低位，再把它转成long long。直接用long long来计算。long long爆掉了会让符号位出错，但是小于2^63的位是不会挂的，这正好符合我们的需求。

ll mul(ll a,ll b,ll p){
	a=(a<0)?a+p:a;
	b=(b<0)?b+p:b;
    ll tmp=(a*b-(ll)((long double)a/p*b+1e-8)*p);
    return tmp<0?tmp+p:(tmp>=p?tmp-p:tmp);
}

把a*b%p变成a*b-(a*b div p * p)，过程用long double算，之后强转long long