a的b次方，结果取m的模

2019-04-13 15:05发布

站内文章 / 模拟电子
16964 0 1778
long long mul_mod(long long a,long long b,long long m) //a个b相加，结果对m取模 { long long t=0; while(b) { if(b&1) { t+= a%m; t%=m; } a<<=1; b>>=1; a%=m; } return t; } long long pow_mod(long long a,long long b,long long m) //a的b次方，并对结果取模 { long long ans=1; while(b) { if(b&1) { ans=mul_mod(ans,a,m);b--; } a=mul_mod(a,a,m); b>>=1; } return ans; }
当a与b很大时，就不得不用此方法了。背下。 还有一种方法： int pow_mod(int a,int n,int m) { if(n==1) return a; else { int x=pow_mod(int a,int n/2,int m) long long x=(long long)x*x%m; if(n%2==1) x=(long long)x*a%m; return (int)x; } }


热门文章