$ 第二板块 $ $ 编程技巧 $

目录

1.快速乘

# include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL a, b, p;

LL qadd(LL a, LL b, LL p){ // a * b % p
    LL res = 0;
    while(b){
        if(b & 1) res = (res + a) % p;

        a = (a + a) % p;
        b >>= 1;
    }

    return res;
}

int main(){
    scanf("%lld %lld %lld", &a, &b, &p);

    printf("%lld", qadd(a, b, p));

    return 0;
}

2.快速幂

# include <bits/stdc++.h>
using namespace std;

typedef long long LL; 

LL a, b, p, ans, base;

LL qpow(LL a, LL b, LL p){
    LL res = 1;
    while(b){
        if(b & 1) res = (res * a) % p;
        a = a * a % p;
        b >>= 1;
    }

    return res;
}

int main(){
    scanf("%lld %lld %lld", &a, &b, &p);
    printf("%lld", qpow(a, b, p) % p); //必需%p,因为b可能为0,p可能为1

    return 0;
}