Ich habe versucht, AOJs Integer-Theorie mit Python zu lösen

Einführung

Hallo. Es ist zäh und zäh. Ich habe versucht, AOJs Integer-Theorie mit Python zu lösen.

Es ist weniger als ein halbes Jahr her, seit ich anfing, mich selbst mit dem Programmieren zu beschäftigen AtCoder ist grün, also bin ich kein starker Mann.

Da es nur wenige Artikel über AOJ gibt, meine Aufzeichnung Ich hoffe, dass das Python-Team die Menschen unterstützt, die in Zukunft ihr Bestes geben werden. Ich habe es zusammen versucht.

Ah, lass uns gehen

Inhaltsverzeichnis

NTL_1_A : Prime Factorization NTL_1_B : Power NTL_1_C : Least Common Multiple NTL_1_D : Euler's Phi Function NTL_1_E : Extended Euclid Algorithm

NTL_1_A : Prime Factorization

#Eingang
n = int(input())

#Primfaktor-Zerlegung und Speicherfaktoren in der Liste
def fac(n):
    f_n = n
    l = []
    if n==1:
        l.append(1)
        exit()
    
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            n //= i
            l.append(i)
    if n!=1:
        l.append(n)
    
    return print("{0}:".format(f_n),*l)

fac(n)

NTL_1_B : Power

 #pow tsuyo oi
m,n = map(int,input().split())
mod = 10**9+7

print(pow(m,n,mod))

NTL_1_C : Least Common Multiple

n = int(input())
a = list(map(int,input().split()))

#gcd und lcm Funktionen
def gcd(a,b):
    a,b = min(a,b), max(a,b)
    while b!=0:
        a,b=b,a%b
    return a

def lcm(a,b):
    return a*b//gcd(a,b)

from functools import reduce
ans = reduce(lcm,a)
print(ans)

NTL_1_D : Euler's Phi Function

Es scheint so etwas zu geben ↓ Eulers φ-Funktion (https://mathtrain.jp/phi)

n = int(input())
l = []
def fac(n):
    if n==1:
        l.append(1)
        exit()
    else:
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                while n%i==0:
                    n //= i    
                l.append(i)
        
        if n!=1:
            l.append(n)
    
    return l

fac(n)
ans = n
for i in l:
    ans *= (1-1/i)
print(int(ans))

NTL_1_E : Extended Euclid Algorithm

Dieser Artikel ist leicht zu verstehen. Ich bin immer verschuldet. Erweiterte euklidische gegenseitige Aufteilung (https://qiita.com/drken/items/b97ff231e43bce50199a)

#Erweiterter Euklidisch
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



x,y = map(int,input().split())
a,b,c = egcd(x,y)

if x==y:
    print(0,1)
    exit()

print(b,c)

abschließend

Dies ist mein erster Artikel, also sei sanft