首页 > 代码库 > POJ 1995 (快速幂)

POJ 1995 (快速幂)

这道题普通做法会发生溢出且会超时,应当用快速幂来求解。

快速幂讲解

 1 #include <cstdio> 2 #include <cmath> 3 using namespace std; 4 int main(){ 5     int Z; 6     scanf("%d",&Z); 7     while(Z--){ 8         int M, H; 9         unsigned long long sum  = 0;10         scanf("%d%d",&M,&H);11         for(int i = 0; i < H; i++){12             long long a,b;13             scanf("%lld%lld",&a,&b);14             long long  ans = 1;15             while(b){16                 if(b&1){17                     ans = (ans * a)%M;18                     b--;19                 }20                 b/=2;21                 a = (a*a)%M;22             }23             sum += (ans%M);24         }25         printf("%llu\n",sum%M);26     }27     return 0;28 }

 

POJ 1995 (快速幂)