ACM-较大的数乘法取模技巧*

2019-04-13 17:06发布

class="markdown_views prism-github-gist"> (有任何问题欢迎留言或私聊 && 欢迎交流讨论哦  比如模数是1e15这种,相乘的时候爆LL了,但是又不想用大数,咋办呢?

文章目录


###快速乘
类似快速幂,很好敲,但是多了一个log!here long long ksc(long long a, long long b, long long mod){ long long res = 0; while(b){ if(b&1) res = (res + a)%mod; (a<<=1)%=mod; b >>= 1; } return res; } ###模拟
找一个较小的数模拟一波 here LL qsc(LL x,LL y){ LL a1=x/1000000,a2=x%1000000,b1=y/1000000,b2=y%1000000; LL t=a1*b1%p*1000000%p*1000000%p; t=(t+a2*b2%p); t=(t+a1*b2%p*1000000%p); t=(t+a2*b1%p*1000000%p); return t%p; } ###转long double再搞回来
《算法竞赛进阶指南》
听说很稳?
ab  mod  p=ababppa∗b;mod ;p = a∗b−⌊frac{a∗b}{p}⌋*p
用long double来计算abp⌊frac{a∗b}{p}⌋,误差很小,因为long double的特性是存不下就舍弃低位,再把它转成long long。直接用long long来计算。long long爆掉了会让符号位出错,但是小于2^63的位是不会挂的,这正好符合我们的需求。 LL mul(LL a,LL b,LL mo){ LL tmp=(a*b-(LL)((long double)a/mo*b+1e-8)*mo); return tmp<0?tmp+mo:(tmp>=mo?tmp-mo:tmp); } LL mul(LL x, LL y,LL mo) { LL z = (long double) x * y / mo; z = x * y - z * mo; if(z < 0) z += mo; else if(z > mo) z -= mo; return z; } https://blog.csdn.net/WerKeyTom_FTD/article/details/50437196
https://blog.csdn.net/alan_cty/article/category/613965