蓝桥杯 第二十二天 数论

目录

1.1246. 等差数列 – AcWing题库

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
n=int(input())
a=list(map(int,input().split()))
a.sort()
if a[0]==a[-1]:
    print(n)
else:
    change=[a[i+1]-a[i] for i in range(n-1)]
    ans=gcd(change[0],change[1])
    for i in range(2,n-1):
        ans=gcd(ans,change[i])
    print((a[-1]-a[0])//ans+1)

2.1295. X的因子链 – AcWing题库

prime=[]
cnt=0
N=pow(2,20)+5
pre=[-1 for i in range(N+1)]
st=[False for i in range(N+1)]
def get_prime(n):
    global cnt
    for i in range(2,n+1):
        if not st[i]:
            pre[i]=i
            prime.append(i)
            cnt+=1
        for j in range(cnt):
            if i*prime[j]>n:
                break
            st[i*prime[j]]=True
            pre[i*prime[j]]=prime[j]
get_prime(N)

def mul(n):
    if n==1:
        return n
    else:
        return n*mul(n-1)

try:
    while True:
        n = int(input())
        whole=0
        a=[0 for i in range(N)]
        if n==1:
            print(1,1)
        else:
            while n!=1:
                whole+=1
                a[pre[n]]+=1
                n//=pre[n]
        ans=mul(whole)
        for i in a:
            if i!=0:
                ans//=mul(i)
        print(whole,ans)
except EOFError:
    pass

3.1296. 聪明的燕姿 – AcWing题库

实现了功能，但是还要封装一下

N=int(2e3+2)
prime=[]
cnt=0

pre=[-1 for i in range(N)]
st=[False for i in range(N)]

def getprime(n):
    global cnt
    for i in range(2,N):
        if not st[i]:
            prime.append(i)
            cnt+=1
            pre[i]=i
        for j in range(cnt):
            if i*prime[j]>=N:
                break
            st[i*prime[j]]=True
            pre[i*prime[j]]=prime[j]
getprime(N)
m=int(input())
a=[]
b=[]
num=-1
while m!=1:
    a.append(pre[m])
    prem=pre[m]
    num+=1
    m//=pre[m]
    while m%prem==0 and m!=1:
        a.append(prem)
        m//=prem
def dfs(start,path):
    global ans
    res=1
    for i in path:
        res*=i
    ans+=res
    print(path,ans)
    cur=[False for i in range(max(a)+1)]
    for i in range(start,len(a)):
        if not st[i] and not cur[a[i]]:
            cur[a[i]]=True
            st[i]=True
            dfs(i+1,path+[a[i]])
            st[i]=False
    return
ans=0
dfs(0,[])
print(ans)