DESCRIPTION

对于

    \[a^n \pmod p\]

p为素数,可以使用费马小定理降幂:

    \[a^n \equiv a^{n \mod {p-1}} \pmod p\]

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

#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

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注