高幂模求解 / High Power Modular Exponentiation Solution

import sys
import math

#参考文献：https://www.cnblogs.com/linyujun/p/5194170.html

print("************程序功能************")
print("求 【X^Y mod Z】 的值")
print("********************************")

print("Reference books: https://www.cnblogs.com/linyujun/p/5194170.html")
print("Reference books: https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0/1944850?fr=aladdin#3_6")
print("Completion time：2021-5-25")
print("Last modification time ：2021-5-25",'\n')
print("--------------------------------------------------------")

print("请输入X：")
X = input()
X = int(X)

print("请输入Y：")
Y = input()
Y = int(Y)

print("请输入Z：")
Z = input()
Z = int(Z)

judge = 0 #接受Z是否为素数指令,0表示Z为素数，1表示Z不为素数

#判断Z是否为素数,并求出素数个数
def judge_sushu(P):
    if (P==2 or P==3):
        return (0)
    dim = int(P**0.5)+1 #必须使用+1，不能使用ceil，否则4时出错
    for i in range(2,dim):
        if (P%i != 0 and i<(dim-1)):
            continue
        elif(P%i!=0 and i==(dim-1)):
            return (0)    #返回1说明P为素数
        else:
            return (i)

Prime_matrix = []

P = Z
Factor = judge_sushu(P)
if (Factor != 0):
    judge = 1
    while(1):
        Prime_matrix.append(int(Factor))
        P = P/Factor
        if (judge_sushu(P) == 0):
            Prime_matrix.append(int(P))
            break
        else: 
            Factor = judge_sushu(P)
else:
    Prime_matrix.append(int(Z))

#求结果
Prime_set = list(set(Prime_matrix))
phi = Z
for i in range(len(Prime_set)):
    phi = phi-phi/Prime_set[i] #欧拉函数值

ans = (int(X%Z)**int(phi+(Y%phi)))%Z #必须加上int，否则会转换成float类型，超出限制
print("结果为：")
print(ans)