poj 1995 快速幂【裸】

最新推荐文章于 2020-08-21 01:03:27 发布

mars_ch

最新推荐文章于 2020-08-21 01:03:27 发布

阅读量1.5k

点赞数 1

分类专栏：乱搞

本文链接：https://blog.csdn.net/mars_ch/article/details/51834704

版权

乱搞专栏收录该内容

8 篇文章

订阅专栏

那么我们就来说一说快速幂吧
a^b
1.如果b是偶数，我们可以记k = a2 mod c，那么求(k)b/2 mod c就可以了。

2.如果b是奇数，我们也可以记k = a2 mod c，那么求

((k)b/2 mod c × a ) mod c =((k)b/2 mod c * a) mod c 就可以了。

那么我们可以得到以下算法：

int ans = 1;

a = a % c;

if(b%2==1) ans = (ans * a) mod c; //如果是奇数，要多求一步，可以提前算到ans中

k = (a*a) % c; //我们取a2而不是a

for(int i = 1;i<=b/2;i++)

{

ans = (ans * k) % c;

}

ans = ans % c;

那么快速幂算法就可以由上一个

int ans = 1;

a = a % c;

while(b>0)

{

if(b % 2 == 1)

ans = (ans * a) % c;

b = b/2;

a = (a * a) % c;

}

那么代码就有了

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
//by mars_ch
using namespace std;
ll a,b,ans;
int n,m;
ll poww(ll a,ll b)
{
    ll res=1;
    int now=a%n;
    while(b)
    {
        if(b & 1)
        {
            res=(res*now)%n;
        }
        now=now*now%n;
        b>>=1;
    }
    return res;
}
int main()
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        ans=0;  
        scanf("%d%d",&n,&m);  
        for(int i=0;i<m;i++)  
        {  
            long long a,b;  
            scanf("%I64d%I64d",&a,&b);  
            ans=(ans+poww(a,b))%n;  
        }  
        printf("%I64d\n",ans);  
    }  
    return 0;  
}