【poj1995】Raising Modulo Numbers

problem

T组数据，每组包含n对ai,bi和一个p。
每组输出一个答案，∑ni=1aibi%p $\underset{i=1}{\overset{n}{\sum }}a{i}^{bi}\mathrm{\%}p$。

solution

快速幂模板。

1.把b拆成二进制形如101110之类，设b有k位，则b = ck−1∗2k−1+ck−2∗2k−2...+c0∗20 $c_{k-1}\ast 2^{k-1}+c_{k-2}\ast 2^{k-2}...+c_0\ast 2^0$
2.ab=ack−1∗2k−1∗ack−1∗2k−2.... $a^b=a^{c_{k-1}\ast 2^{k-1}}\ast a^{c_{k-1}\ast 2^{k-2}}....$
3.因为a2i=(a2i−1)2 $a^{2^i}=(a^{2^{i-1}}{)}^2$ ,所以偶数时直接*2，奇数多乘一个a就好了。

codes

#include<iostream>
using namespace std;
typedef long long LL;
LL pow(LL a, LL b, LL p){
    LL x = 1;
    while(b){
        if(b&1)x = x*a%p;
        a = a*a%p;
        b >>= 1;
    }
    return x%p;
}
int main(){
    int _w;  cin>>_w;
    while(_w--){
        int n, p;  cin>>p>>n;
        LL ans = 0;
        for(int i = 1; i <= n; i++){
            int a, b;  cin>>a>>b;
            ans = (ans+pow(a,b,p))%p;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80390794