首页 > 其他 > 详细

FZU 1752 a^b%c

时间:2015-08-03 19:15:51      阅读:303      评论:0      收藏:0      [点我收藏+]

题目连接:http://acm.fzu.edu.cn/problem.php?pid=1752
解题思路:要用快速幂,但不是单纯的用,如果单纯的用的话就会爆掉,要把乘法转化为加法,然后再用而且尽量用位运算。。。
上代码:

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL multi(LL a, LL b, LL c)
{
    LL ans=0;
    a=a%c;
    while(b)
    {
        if(b&1)
        {
            ans+=a;//ans=(ans+a)%c;
            if(ans>=c)
            ans-=c;
        }

        a<<=1;//a=(a+a)%c;
        if(a>=c)
        a-=c;
        b>>=1;
    }
    return ans;
}
LL quick(LL a, LL b, LL c)
{
    LL ans=1;
    while(b)
    {
        if(b&1)
        ans=multi(ans, a, c);
        a=multi(a, a, c);
        b>>=1;
    }
    return ans;
}
int main()
{
     LL n,m,mod;
     while(~scanf("%I64d%I64d%I64d",&n,&m,&mod))
     {
        printf("%I64d\n", quick(n, m, mod));
     }
    return 0;
}
//100000000000000000

版权声明:本文为博主原创文章,未经博主允许不得转载。

FZU 1752 a^b%c

原文:http://blog.csdn.net/qingshui23/article/details/47258941

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!