J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python

introduction

Bonjour. C'est moelleux et moelleux. J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python.

Cela fait moins d'un an et demi que j'ai commencé à toucher la programmation moi-même AtCoder est vert, donc je ne suis pas un homme fort.

Puisqu'il y a peu d'articles sur AOJ, mon dossier J'espère que l'équipe Python soutiendra les personnes qui feront de leur mieux à l'avenir. J'ai essayé ensemble.

Ah, allons-y

table des matières

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

#contribution
n = int(input())

#Décomposition des facteurs premiers et stocker les facteurs dans la 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()))

#fonctions gcd et lcm
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

Il semble y avoir quelque chose comme ça ↓ Fonction φ d'Euler (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

Cet article est facile à comprendre. Je suis toujours redevable. Division mutuelle euclidienne étendue (https://qiita.com/drken/items/b97ff231e43bce50199a)

#Euclidienne étendue
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)

en conclusion

Ceci est mon premier article, alors soyez doux