高次方取模(template)

2019-04-13 15:41发布

站内文章 / 模拟电子
16711 0 1656
就是求（a^b）% p ，a,b,p比较大
取余公式：（a*b）%p=（a%p*b%p）%p
算法核心就是下面两个公式：
这里写图片描述 //次方求模模板 template<class Type> inline Type ModPow(Type m,Type n,Type p) //m的n次方模p { if(n==0) return 1; if (n==1) return m%p; Type tmp=ModPow(m,n>>1,p); return (tmp*tmp%p)*((n%2?m:1)%p)%p; } //REF：[C小加](http://www.cppblog.com/cxiaojia/archive/2012/04/06/170268.html) /*高次方求模： 比如a的b次方对c求模 我们可以把b 化为二进制形式看那一位有1 比如b=10101则 a^b=a^(10000)*a^(100)*a^(1) 以函数形式体现：*/ template<class Type> inline Type han() { Type t,s; for(t=a,s=1;b;b>>=1,t*=t,t%=c)//用b>>=1查看b中1 if(b&1){s*=t;s%=c;} return s%c; } //REF:[知行执行](http://www.cnblogs.com/zhixingqiezhixing/archive/2012/02/18/2356655.html) btw , 大数取模的模板
取余公式：（a+b）%p=(a%p+b%p)%p; char big_number[MAX]; template<class type> type big_mod(char *a,type mod){ type len=strlen(a),result=0; for(int i=0;i10)%mod+(a[i]-'0')%mod)%mod; //如果数据不算太大，可以写成这样来节省时间result=(result*10+a[i]-'0')%mod; } return result; } //test char s[200]; int main() { while(gets(s)) cout<int>(s,2)<

热门文章