1.快速幂------求a^s%mod
1）a，b都是int型
1 long long solve(int a,int b,int mod) 2 { 3 long long ans=1; 4 while(b!=0)//b>0 5 { 6 if(b&1)//说明b为奇数，分成a*ans 7 ans=(ans*a)%mod; 8 a=a*a; 9 b>>=1; 10 } 11 return ans; 12 }
2）a是long long 类型，s是大数，为字符串类型。
#include<iostream> #include<algorithm> #include<string> #include<string.h> using namespace std; const int mod=1e9+7; long long quick_mod(long long a,long long b) { long long ans=1; while(b){ if(b&1){ ans=(ans*a)%mod; b--; } b/=2; a=a*a%mod; } return ans; }//内部也用快速幂 long long quickmod(long long a,char *b,int len) { long long ans=1; while(len>0){ if(b[len-1]!=‘0‘){ int s=b[len-1]-‘0‘; ans=ans*quick_mod(a,s)%mod; } a=quick_mod(a,10)%mod; len--; } return ans; } int main(){ char s[100050]; int a; while(~scanf("%d",&a)) //求a^s%mod { scanf("%s",s); int len=strlen(s); printf("%I64d\n",quickmod(a,s,len)); } return 0; }
3）矩阵快速幂
原文：https://www.cnblogs.com/Aiahtwo/p/10832437.html
