Hello. It's chewy and chewy. I tried to solve AOJ's number theory in Python.
It's been less than half a year since I started programming myself AtCoder is green, so I'm not a strong man.
Since there are few articles on AOJ, my record I hope it will support the comrades who will do their best with Python. I tried together.
Ah, let's go
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
#input
n = int(input())
#Factors into prime factors and stores the factors in a list
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 and lcm functions
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
There seems to be something like this ↓ Euler's φ function (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
This article is easy to understand. I am always indebted. Extended Euclidean algorithm (https://qiita.com/drken/items/b97ff231e43bce50199a)
#Extended Euclid
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)
This is my first article, so be gentle
Recommended Posts