TSOJ 1509 – 十进制快速幂

DESCRIPTION

对于

当为素数，可以使用费马小定理降幂：

当为合数，可以使用十进制快速幂解决。

#include <bits/stdc++.h>

#define LL long long
#define LD long double

inline LL mul(LL a, LL b, LL mod) {
    return (a * b - (LL)((LD)a / mod * b) * mod + mod) % mod;
}

inline LL mod_pow(LL a, LL b, LL mod) {
    if (b == 0) {
        return 1;
    }
    for (; ~b & 1; a = mul(a, a, mod), b >>= 1);
    LL ret = a;
    for (b >>= 1; b; b >>= 1) {
        a = mul(a, a, mod), (b & 1) ? ret = mul(ret, a, mod) : 0;
    }
    return ret;
}

inline LL mod_pow_solve(LL a, char *b, LL mod) {
    LL ret = 1;
    int len = strlen(b);
    for (int i = len - 1; i >= 0; --i) {
        ret = mul(ret, mod_pow(a, b[i] ^ '0', mod), mod), a = mod_pow(a, 10, mod);
    }
    return ret;
}

int main() {
    int a;
    char s[300];
    while (~scanf("%d %s", &a, s)) {
        printf("%d\n", mod_pow_solve(a, s, 1337));
    }
    return 0;
}

SUMMARY

留一个坑，期末考完再填。

REFERENCE

https://blog.csdn.net/scar_lyw/article/details/70169737

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.