【poj1995】Raising Modulo Numbers

            

problem

T组数据,每组包含n对ai,bi和一个p。
每组输出一个答案,<span class="MathJax" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="

i=1naibi%p

" role="presentation" style="position: relative;">

i=1naibi%p

solution

快速幂模板。

1.把b拆成二进制形如101110之类,设b有k位,则b = ck12k1+ck22k2...+c020

" role="presentation" style="position: relative;">

ck12k1+ck22k2...+c020


2.ab=ack12k1ack12k2....

" role="presentation" style="position: relative;">

ab=ack12k1ack12k2....


3.因为a2i=(a2i1)2

" role="presentation" style="position: relative;">

a2i=(a2i1)2

,所以偶数时直接*2,奇数多乘一个a就好了。

codes

#include
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<'\n';
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像