首页 > 代码库 > 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 (快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。