code notes

因式分解

def factorization(num):
    factor=[]
    while num>1:
        for i in range(num-1):
            k=i+2
            if num%k==0:
                factor.append(k)
                num//=k
                break
    return factor

快速幂取余

def quickpow(n,m,k):  #n为底数，m为指数，对k取余
    n=n%k
    res=1
    while m:
        if m&1:
            res=res*n%k
        m>>=1
        n=n*n%k
    return res

最长上升子序列打印路径

def longestupseq(arr):
    if not arr:
        return 0
    n=len(arr)
    dp=[1 for _ in range(n)]
    maxlen=1
    end=0
    for i in range(n):
        for j in range(i):
            if arr[j]<arr[i]:
                dp[i]=max(dp[j]+1,dp[i])
                if dp[i]>maxlen:
                    end=i
                    maxlen=dp[i]

    res=[]
    res.append(arr[end])
    for i in range(end,-1,-1):
        if dp[i]==maxlen-1:
            res.append(arr[i])
            maxlen-=1
    return res[::-1]

arr=[10,9,2,5,3,7,101,18]
print(longestupseq(arr))