快速幂

快速幂取模算法可以在O(log2b)的时间内求出ab mod p的值。 运用了二进制的思想，实质是对b进行二进制分解。 代码： typedef long long LL; LL ksm(int a,int b,int p)//最好不要把函数名取成power、modpower之类的，考试的时候可能会挂233 { LL res=1; while(b) { if(b&1) res=res*a%p;//如果b是奇数，或者说当前这一位二进制是1 a=a*a%p;//计算a^2,a^4,a^8,a^16...,a^(2^i) b>>=1;//b除以2，或者说处理下一位二进制 } return res; }

快（龟）速乘法

“快”读作“龟”（雾 在O(log2b)的时间内求a×b mod p。由于直接乘是O(1)的时间复杂度，所以又被叫做“龟速乘法”。 主要用途是解决大数相乘，而且模数较大的问题。如两个1e18级别的数相乘，模数也是1e18级别。任凭你怎么取模，最后还是要爆long long。解决方法之一是写高精度乘法和高精度取模。但是我很懒，并不想写高精度。那该怎么办？可以把乘法转化成加法。我一个个地在答案上加a，每加一个a取一次模，这样总不会爆long long了吧！但是这样的时间复杂度太高，估计算一辈子也算不完。我们可以借助快速幂的思想，创造一种“快速乘法”算法，就是把快速幂里面所有的乘号换成加号。 再强调一遍，虽然这个算法被叫做“快速乘法”，但是它并不如直接做乘法快！ 代码： typedef long long LL; LL ksc(int a,int b,int p)//拼音大法好 { LL res=0;//注意初始答案是0而不是1 while(b) { if(b&1) res=(res+a)%p; a=(a+a)%p; b>>=1; } return res; }