• 1.问题描述
• 2.问题分析
• 3.算法设计
• 4.确定程序框架
• 5.完整的程序

1．问题描述

求13的13次方的最后三位数。

2．问题分析

许多初学者看到本题最容易想到的方法就是：将13累乘13次后截取最后三位即可。但是计算机中存储的整数是有一定范围的，超出某范围将不能正确表示，所以用这种算法不可能得到正确的结果。实际上，题目仅要求后三位的值，完全没有必要把13的13次方完全求出来。

3．算法设计

手工计算13的13次方的步骤如下：

研究乘法的规律可以发现，乘积的最后三位的值只与乘数和被乘数的后三位有关，与乘数和被乘数的高位无关。利用这一规律，在计算下一次的乘积时，我们只需用上次乘积的后三位来参与运算（即在求第三次乘积时，上次的乘积2197并不需要都参与运算，只取其后三位197再次与13相乘即可）。求某数的后三位的算法为：用某数对1000取模。

编程中，将累乘得到的积存储到变量last中，在进行下一次相乘之前先截取last的后三位再相乘，即last%1000*13，将结果存储到last中，即last=last*x%1000，这里x的值为13。因第一次相乘时用到了变量last的初值，故在定义时给last赋初值1，或在参与计算之前给last赋初值1。

4．确定程序框架

程序流程图如图所示。

5．完整的程序

%%time
# 高次方数的尾数

if __name__ == "__main__":
    last = 1                                        # 变量last保存求得的x的y次方的部分积的后三位
    print("请输入两个数x和y：")
    x = int(input("x = "))
    y = int(input("y = "))
    print(f'x={x},y={y}')
    for i in range(1, y+1):
        last = last * x % 1000      # 将last乘x后对1000取模，即求积的后三位
    print("%d的%d次方所得积的后三位为：%d" %(x,y,last))

请输入两个数x和y：
x=13,y=13
13的13次方所得积的后三位为：253
CPU times: user 41.1 ms, sys: 12.6 ms, total: 53.7 ms
Wall time: 4.53 s

上述程序段具有普遍性，无论是求哪个数的多少次方的后三位尾数都可以利用上述程序实现。若针对本题中的具体数据，程序可改为：

# 高次方数的尾数

if __name__ == "__main__":
    last = 1                                # 变量last保存求得的13的13次方的部分积的后三位
    for i in range(1, 13+1):        # 13自乘的次数
        last = last * 13 % 1000     # 将last乘13后对1000取模，即求积的后三位
    print("13的13次方所得积的后三位为：%d" %last)

13的13次方所得积的后三位为：253