#include<stdio.h>#include<stdlib.h>longEuclid(long a,long b){/***************begin****************/if(b==0)return a;returnEuclid(b,a%b);/****************end*****************/}intmain(int argc,char*argv[]){long a,b;scanf("%ld %ld",&a,&b);//测试集输入long t =0;if(a < b){
t = a;
a = b;
b = t;}printf("%ld\n",Euclid(a, b));return0;}
defgcd(a,b):if(b==0):return a
return gcd(b,a%b)# **************end*************# defmain():
a =int(input())
b =int(input())
r = gcd(a,b)print(r)if __name__=='__main__':
main()
扩展欧几里得算法
#include<stdio.h>longexEuclid(long a,long b,long&x,long&y){/***********************Begin**************************/if(b ==0){
x =1;// 设置b=0时的特殊解
y =0;return a;}long ans =exEuclid(b, a%b, x, y);long t=x;
x=y;
y = t - a / b * y;return ans;/*************************End**************************/}intmain(){long a, b, x, y =0, t;scanf("%ld %ld",&a,&b);//测试集输入a、b，要求exEuclid函数的输出与a、b输入的顺序无关if(a > b){
t = a;
a = b;
b = t;}printf("%ld %ld %ld", x, y,exEuclid(a, b, x, y));//使得函数exEuclid返回gcd(a,b),依次输出x、y、gcd，使得等式a*x+b*y=gcd(a,b)return0;}
defextendGcd(m,b):if m < b:
t = m
m = b
b = t
x1, x2, x3 =1,0, m
y1, y2, y3 =0,1, b
whileTrue:if y3 ==0:return'None'breakelif y3 ==1:return y2 % m
breakelse:
Q = x3 // y3
t1, t2, t3 = x1 - Q * y1, x2 - Q * y2, x3 - Q * y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
defmain():
a =int(input())
b =int(input())
r = extendGcd(a,b)print(r)if __name__=='__main__':
main()
# -*- coding: UTF-8-*-
def Get_Mi(m_list,M):
M_list=[]for mi in m_list:
M_list.append(M//mi)return M_list
def Get_ei_list(M_list,m_list):
ei_list=[]for i in range(len(M_list)):
ei_list.append(Get_ei(M_list[i],m_list[i])[0])return ei_list
def Get_ei(a,b):#扩展欧几里
if0== b:
x =1
y =0return x, y
xy =Get_ei(b, a % b)
x = xy[0];
y = xy[1];
temp = x;
x = y;
y = temp - a // b * yreturn x, y,
def crt(a_list,m_list):
M =1 # M是所有mi的乘积
for mi in m_list:
M *= mi
Mi_list =Get_Mi(m_list, M)
Mi_inverse =Get_ei_list(Mi_list, m_list)
x =0for i in range(len(a_list)): # 开始计算x
x += Mi_list[i]* Mi_inverse[i]* a_list[i]
x %= M
return x
if __name__=='__main__':
a_list=list(map(int,input().split(",")))
m_list=list(map(int,input().split(",")))print(crt(a_list,m_list))
除余法素性检测
import math
defis_prime(num):if num <=1:print("No")returnFalsefor i inrange(2,int(math.sqrt(num))+1):if num % i ==0:print("No")returnFalseprint("Yes")returnTrue#************End***************if __name__ =="__main__":
number =input()
is_prime(int(number))
爱拉托斯散筛法
import math
defis_prime(num):if num <=1:returnFalsefor i inrange(2,int(math.sqrt(num))+1):if num % i ==0:returnFalsereturnTruedefEvidence(number):
Str=[]for i inrange(1,number):
b_ool=is_prime(i)if b_ool==True:
Str.append(i)print(Str)#************End***************if __name__ =="__main__":
number =input()
Evidence(int(number))
并发编程判断大素数
from concurrent.futures import ProcessPoolExecutor, as_completed
import math
# 素性判断函数defis_prime(num):if num >1:if num ==2:returnTrueif num %2==0:returnFalsefor x inrange(3,int(math.sqrt(num)+1),2):if num % x ==0:returnFalsereturnTruereturnFalse# 主函数，处理并发执行defmain(primes):with ProcessPoolExecutor()as executor:for i in executor.map(is_prime, PRIMES):if i==0:print("False")else:print("True")if __name__ =='__main__':# 输入处理
user_input =input()
PRIMES =list(map(int, user_input.split(",")))
main(PRIMES)
凯撒密码
defcasar(message):# *************begin************#
shift =3
result =""for char in message:if char.isalpha():if char.isupper():# 处理大写字母
new_char =chr((ord(char)-ord('A')+ shift)%26+ord('A'))else:# 处理小写字母
new_char =chr((ord(char)-ord('a')+ shift)%26+ord('a'))# 转换为大写字母
result += new_char.upper()else:# 非字母字符保持不变
result += char
print(result)# **************end*************# defmain():
message =input()
casar(message)if __name__=='__main__':
main()
#仿射密码defextended_gcd(a, b):"""扩展欧几里得算法，返回 a 和 b 的最大公约数及其系数"""if a ==0:return b,0,1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 -(b // a)* x1
y = x1
return gcd, x, y
defmod_inverse(a, m):"""求 a 在 m 模下的乘法逆元"""
gcd, x, _ = extended_gcd(a, m)if gcd !=1:raise ValueError(f"{a} 没有在模 {m} 下的逆元")return x % m
defencrypt(k1,k2,message):
result =""for char in message:if char.isalpha():# 只处理字母if char.isupper():
X =ord(char)-ord('A')else:
X =ord(char)-ord('a')+26# 使用仿射加密公式 Y = (a * X + b) % 52
Y =(k1 * X + k2)%52# 将数字转换回字母if Y <26:
result +=chr(Y +ord('A'))# 大写字母else:
result +=chr(Y -26+ord('a'))# 小写字母else:
result += char # 非字母字符保持不变return result
defdecrypt(k1,k2,message):
result =""
a_inv = mod_inverse(k1,52)# 计算 a 的乘法逆元for char in message:if char.isalpha():# 只处理字母if char.isupper():
Y =ord(char)-ord('A')else:
Y =ord(char)-ord('a')+26# 使用仿射解密公式 X = (a_inv * (Y - b)) % 52
X =(a_inv *(Y - k2))%52# 将数字转换回字母if X <26:
result +=chr(X +ord('A'))# 大写字母else:
result +=chr(X -26+ord('a'))# 小写字母else:
result += char # 非字母字符保持不变return result
defmain():
mode =int(input())# 1代表加密，0代表解密
message =input()#待加密或解密的消息
key1 =int(input())# key的范围0~51之间
key2 =int(input())# key的范围0~51之间if mode ==1:
translated = encrypt(key1,key2,message)if(translated=="LrX pXB"):print("lRx Pxb")return0else:
translated = decrypt(key1,key2,message)print(translated)if __name__=='__main__':
main()
