题目

自己在大部分题解公式的基础上提了一个m，然后想用普通的快速幂做，但是考虑到如果一律$mod$ $100003$可能导致$m^ {n - 1} - (m - 1) ^ {n - 1}$出现负数，就想多保留一位，但是wtcl不知道怎么做，只好$mod$了$1000030$

#include <cstdio>

long long fst(long long a, long long b)
{
    long long base = a, ans = 1;
    while(b)
    {
        if(b & 1)
            ans *= base;
        base *= base;
        ans %= 1000030;
        base %= 1000030;
        b >>= 1;
    }
    return ans;
}
int main()
{
    long long m, n;
    scanf("%lld %lld", &m, &n);
    printf("%lld", m * ((fst(m, n - 1) - fst(m - 1, n - 1) % 100003)) % 100003);
    return 0;
}

很神奇地A了……

然后试图换成$mod$ $100003$提高效率

#include <cstdio>

long long fst(long long a, long long b)
{
    long long base = a, ans = 1;
    while(b)
    {
        if(b & 1)
            ans *= base;
        base *= base;
        ans %= 100003;
        base %= 100003;
        b >>= 1;
    }
    return ans;
}
int main()
{
    long long m, n;
    scanf("%lld %lld", &m, &n);
    printf("%lld", m * ((fst(m, n - 1) - fst(m - 1, n - 1) % 100003)) % 100003);
    return 0;
}

结果5$$AC， 5$$WA

想知道这是什么原理，有没有更高效的做法

以及希望有神犇能给出比较好的讲解$mod$ 的博客

初学，问题可能比较zz，求轻喷qwq