模运算
(ab)mod m=(a mod m)(b mod m) mod m
一、刷题统计
a,b,n=map(int,input().split())
res=a*5+b*2
m=n//res*7
n=n%res
t=0
while n>0:
if t<5:
n-=a
m+=1
else:
n-=b
m+=1
print(m)
二、快速幂
b,p,k=map(int,input().split())
def quick_mi(b,p,k):
n=p
b%=k
ans=1
while n:
if n&1==1:
ans=(ans*b)%k
b=(b*b)%k
n>>=1
return ans
print(quick_mi(b,p,k))
三、RSA解密
先用下段代码求解p、q
import math
n=1001733993063167141
k=int(math.sqrt(n))
for i in range(2,k+1):
if n%i==0:
print(i,n//i)
891234941 1123984201
第二步将de%((p-1)(q-1))的式子转换一下
n=1001733993063167141
d=212353
p=891234941
q=1123984201
tmp=(p-1)*(q-1)
print(tmp)
for i in range(2,n+1):
now=i*tmp+1
if now%d==0:
print(now//d)
break
1001733991047948000
823816093931522017
第三步,利用快速幂的代码求解x=c^e mod n
n=1001733993063167141
e=823816093931522017
c=20190324
def fastpow(a,b,mod):
ans=1
while b:
if b&1:
ans=ans*a%mod
a=a*a%mod
b>>=1
return ans
print(fastpow(c,e,n))
579706994112328949
GCD
def gcd(a,b):
if b==0:
return a
return gcd(b,a%b)
def gcd(a,b):
return a if b==0 else gcd(b,a%b)
from math import gcd
LCM
最小公倍数
LCM=a*b/gcd(a,b)
def lcm(a,b):
return a*b//gcd(a,b)
四、核桃的数量(最小公倍数)
这道题就是求a,b,c的最小公倍数
from math import *
def lcm(a,b):
return a*b//gcd(a,b)
a,b,c=map(int,input().split())
ans=lcm(lcm(a,b),c)
print(ans)
五、Hankson 的趣味题
通过了80%,最后一个超时了,没有找到ac的python代码,如果有,麻烦大家发在评论群一下!
import math
from math import gcd
def lcm(a,b):
return a*b//gcd(a,b)
n=int(input())
for i in range(n):
a0,a1,b0,b1=map(int,input().split())
ans=0
for x in range(1,int(math.sqrt(b1)+1)):
if b1%x==0:
if gcd(x,a0)==a1 and lcm(x,b0)==b1:
ans+=1
y=b1//x
if x==y:continue
if gcd(y,a0)==a1 and lcm(y,b0)==b1:
ans+=1
print(ans)
六、寻找整数
之前看别人的写法是找规律,感觉很复杂,但是感觉就是一直寻找他们的最小公倍数,然后累计步长很巧妙!
from math import *
mod=[0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46]
ans=2+mod[2]
k=2
for i in range(3,50):
while True:
if ans%i==mod[i]:
k=lcm(k,int(i))
break
else:ans+=k#一直加他们的最小公倍数,一直到满足符合是其倍数
print(ans)
print(2022040920220409)
素数
七、笨小孩
import math
def check(u):
if u<=1:
return False
for i in range(2,int(math.sqrt(u))+1):
if u%i==0:
return False
return True
letter=[0]*26
s=input()
for i in range(len(s)):
if "A"<=s[i]<"Z":
letter[ord(s[i]) - ord('A')] += 1
else:letter[ord(s[i])-ord('a')]+=1
letter.sort()
maxx=letter[-1]
for i in letter:
if i==0:
continue
minn=i
break
# print(maxx,minn)
if check(maxx-minn):
print("Lucky Word")
print(maxx-minn)
else:
print("No Answer")
print("0")
八、质数
文章来源:https://www.toymoban.com/news/detail-407049.html
N=10**6
primes=[]
bprime=[False]*N
def getPrimes(n):
global primes
global cnt
bprime[0]=True
bprime[1]=True
for i in range(2,n+1):
if not bprime[i]:
primes.append(i)
cnt+=1
for j in range(i*2,n+1,i):
bprime[j]=True
n=int(input())
cnt=0
getPrimes(n-1)
for p in primes:
print(p,end=' ')
print()
print(cnt)
九、分解质因数
文章来源地址https://www.toymoban.com/news/detail-407049.html
到了这里,关于学python的第十五天---简单数论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!