Python实现求n的n次方的后三位怎么求（99999<n<999999）

Python实现求n的n次方的后三位怎么求（99999

n = int(input())
n = str(n ** n)
print(n[-3:])

整数的后三位，实质上就是模运算，相当于 mod 1000，
所以这是一个快速幂的模运算的算法问题，
只需要模运算结果，并不需要完整的中间结果。

模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p

推论：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)；

费马定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p
推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p

def pow(base, exp, mod):  # python的内部函数，使用快速幂算法
    result = 1
    while exp:
        if exp & 1:
            result *= base
            result %= mod
        base *= base
        base %= mod
        exp >>= 1
    return result

n = int(input('输入正整数: '))
n = pow(n, n, 1000)
print(n)

来一个程序员常规解法，既然是三位余数，那么最多余数的可能是 0 ~ 999，最多 1000 个，只要把这些余数枚举出来，查找余数表即可

# 余数   1    2   3   4    5   3   4   5   3    4    5    3    4 
#             循环开始 循环结束                                 
# index  0    1   2   3   4    5   6   7   8   9     10   11   12
# 查找第 12 个，     2 + (12 - 2) % (5 - 2) = 3   第三个就是余数 4

n = int(input())
l = list()
for i in range(1001):        
    r = n ** i % 1000
    if i >= n:    # 如果算到 n ** n 还没有发现循环的余数，结果直接输出即可
        print(r)
        break
    if r in l:    # 否则，寻找 n 在循环余数中的位置就是最终答案
        print(l[l.index(r) + (n - l.index(r)) % (i - l.index(r))])
        break
    l.append(r)

借楼上老哥的用例用一下 PENGCM

❯ & C:/Users/wakea/AppData/Local/Programs/Python/Python310/python.exe d:/wakea/Source/CSDN_Ask/7778233/main.py
1234567890987654321
721

你的代码没什么毛病，只是计算的数字太大了，电脑反应速度有点慢，多等等就好了。
比如，99999**99999，这个数字就有6千多行，一般电脑大概需要10秒以上才能算完。

简化这个代码，因为只需要求后三位，其实数学上就等价于后三位的n次方，可以这样写：
n=int(str(n)[-3:])**n
n=str(n)[-3:]
数字位数越多，节省的时间越多。6位数，大概能节省75%左右。你自己跑跑试试

先不进行幂运算，测试一下乘积运算 比如999999999 * 999999999 **表示幂运算
所需的字符串消耗的内存就是：
999999999 * math.log(999999999, 10) / 8 / 1024 ** 3

如果按照题目所示，进行幂运算计算过程是非常慢的，数字需要转10进制，也需要O(N)次除法，每次O(N)。会等很久的

因为两位数乘以两位数就是四位数，所以决定乘积结果就是每个数的后面两位。于是只需要对n的后两位位数相乘n次即可。

n = int(input('Please enter an integer:'))
res = 1
for i in range(n):
    res = (res % 100)*(n % 100)
print(res % 1000)

分析一下乘法的过程, 就知道结果的低三位最多由因子的低三位影响, 每次计算完取个低三位就好了

import time
time_start = time.time()

n = 999999

res=n
for i in range(n-1):
    res *= n
    res %= 1000

print(f'running time: {time.time()-time_start}s')

运行结果:

running time: 0.20829415321350098s

代码没有问题