简单数论专题

佚名 6年前 (2019-05-08) 随笔 794人围观抢沙发百度已收录

1.快速幂------求a^s%mod

1）a，b都是int型

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 long long solve(int a,int b,int mod)
 2 {
 3     long long ans=1;
 4     while(b!=0)//b>0 
 5     {
 6         if(b&1)//说明b为奇数，分成a*ans
 7         ans=(ans*a)%mod;
 8         a=a*a;
 9         b>>=1;
10     }
11     return ans;
12 }

2）a是long long 类型，s是大数，为字符串类型。

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
const int mod=1e9+7;
long long quick_mod(long long a,long long b)
{
    long long ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
            b--;
        }
        b/=2;
        a=a*a%mod;
    }
    return ans;
}//内部也用快速幂
long long quickmod(long long a,char *b,int len)
{
    long long ans=1;
    while(len>0){
        if(b[len-1]!='0'){
            int s=b[len-1]-'0';
            ans=ans*quick_mod(a,s)%mod;
        }
        a=quick_mod(a,10)%mod;
        len--;
    }
    return ans;
}
int main(){
    char s[100050];
    int a;
    while(~scanf("%d",&a))         //求a^s%mod
    {
        scanf("%s",s);
        int len=strlen(s);
        printf("%I64d\n",quickmod(a,s,len));
    }
    return 0;
}