快速降幂取模

CINTA

定理

$(a * b) \mod p = ((a \mod p)* (b \mod p)) \mod p$

#include <stdio.h>
#include <stdlib.h>
long FastPower(int base, int power,int mod){
    if(base == 1)
        return 1;
    if(base == 0)
        return 0;
    long res = 1;
    while(power){
        if(power & 1)
            res = (res * base) % mod;
        power >>=1;
        //res *= res; 
        base = (base * base) % mod;
    }
    return res % mod;
}
long FastPowerRecursion(int base,int power,int mod){
    if(base == 1)
        return 1;
    if(base == 0)
        return 0;
    if(power == 1) 
        return base;
    if(power &1)
        return (FastPowerRecursion(base*base,power>>1,mod)*base)%mod;
    return (FastPowerRecursion(base*base,power>>1,mod))%mod;
}
int main(){
    long base,power;
    int mod;
    scanf("%ld %ld %d",&base,&power,&mod);
    printf("%ld\n",FastPower(base,power,mod));
    printf("%ld",FastPowerRecursion(base,power,mod));
    return 0;
}