取模运算的性质？

$$(a \times b) \% p = \left[(a \% p) \times (b \% p)\right] \% p$$
证明：
设:$a=k_1p+q_1 , b=k_2p+q_2$
$(a\times b)=(......)\times p+q_1 q_2$
$(a\times b)\%p=(q_1 q_2)\%p$
$a\%p=q_1,b\%p=q_2$

考虑手算$3^{10}$怎么实现？

$3^{10} = (3^2)^5=9^5=9\times 9^4=9\times(81)^2=9\times (81^2)^1$

代码实现

python版本

def func(a, b, k):
    ans = 1
    a %= k
    while b:
        if b % 2 == 1:
            ans = (ans * a) % k
            a = (a * a) % k
            b //= 2
        else:
            a = (a * a) % k
            b //= 2
    return ans


c, d = map(int, input().split())
res = func(c, d, 7)
print(res)

然后可以进行一些优化。比如if和else里面有重合的语句。判断b是否为奇数。还有b整除2可以用位运算提高速度。

def func(a, b, k):
    ans = 1
    a %= k
    while b:
        if b & 1:
            ans = (ans * a) % k
        a = (a * a) % k
        b >>= 1
    return ans


c, d = map(int, input().split())
res = func(c, d, 7)
print(res)

if和else里面重合的语句我们可以提出来。反正无论如何都是需要执行的。
判断b是否是奇数，只需要b和1相与就可以了。因为如果是奇数。二进制最后一位一定是1，和1相与结果就是真。如果是偶数，最后一位一定是0，和1相与就是假。
b整除2，我们二进制右移一位，效果就等价于除以2了。

c++版本

#include<iostream>
using namespace std;
int func(int a, int b, int k)
{
    int ans = 1;
    a %= k;
    while (b)
    {
        if (b & 1)
        {
            ans = (ans * a) % k;
        }
        a = (a * a) % k;
        b >>= 1;
    }
    return ans;
}
int main()
{
    cout << func(3, 2000, 7);
}

和python没什么区别。