NTL_1の解答例(Python)

素因数分解・累乗計算・最小公倍数・オイラーのφ関数・拡張ユークリッド互除法に関する問題です．

1. NTL_1_A: Prime Factorize

# NTL_1_A
# 素因数分解 2から順に割ってみればよい
def PrimeFactorize(n):
    i = 2
    ans = [] # 答えるべき素因数のリスト
    while n>1 and i<n**0.5+1:
        if n%i == 0:
            n = int(n/i)
            ans.append(i) # 割り切れた場合は素因数のリストに追加
            i = 1
            
        i += 1
        
    # 残ったものが1でなければ素数なのでこれも追加する
    if n != 1:
        ans.append(n)
    return ans

n = int(input())
ans = PrimeFactorize(n)
print(f"{n}:",end=" ")
print(*ans)

2. NTL_1_B: Power

# NTL_1_B
import math
m0,n = list(map(int,input().split())) 
m2 = 1
# nが0になるまで繰り返しかけ続ける
while n >= 1:
    cnt = 1
    m = m0
    # 2乗ずつ計算する
    for i in range(int(math.log2(n))):
        m = (m**2)%1000000007
        cnt *= 2

    n = n-cnt
    m2 *= m

print(m2%1000000007)

3. NTL_1_C: Least Common Multiple

# NTL_1_C
# 素因数を求めてそれぞれの約数の個数の最大を取れば最小公倍数

# 素因数分解(辞書バージョン) : 素因数の辞書を返すようにする n=12 なら ans_dict = {2:2, 3:1}
def PrimeFactorize_dict(n):
    i = 2
    ans_dict = {} # 素因数の辞書
    while n>1 and i<n**0.5+1:
        if n%i == 0:
            n = int(n/i)
            # 割り切れた場合は素因数の辞書に追加
            if i not in ans_dict:
                ans_dict[i] = 0 
            ans_dict[i] += 1
            i = 1
            
        i += 1
        
    # 残ったものが1でなければ素数なのでこれも追加する
    if n != 1:
        if n not in ans_dict:
            ans_dict[n] = 0 
        ans_dict[n] += 1
    return ans_dict

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

lcm_dict = {}
for a in A:
    ans_dict = PrimeFactorize_dict(a)
    for i in ans_dict:
        # 素因数の数が最大になるように取っていけばいい
        if i not in lcm_dict:
            lcm_dict[i] = ans_dict[i]
        else:
            lcm_dict[i] = max(lcm_dict[i],ans_dict[i])

# 素数を掛け合わせてlcmを求める
lcm = 1
for i in lcm_dict:
    lcm *= i**lcm_dict[i]
    
print(lcm)

4. NTL_1_D: Euler's Phi Function

# NTL_1_D
# https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0

# 素因数分解 : O(n**0.5)
def PrimeFactorize(n):
    i = 2
    ans = [] # 答えるべき素因数のリスト
    while n>1 and i<n**0.5+1:
        if n%i == 0:
            n = int(n/i)
            ans.append(i) # 割り切れた場合は素因数のリストに追加
            i = 1
            
        i += 1
        
    # 残ったものが1でなければ素数なのでこれも追加する
    if n != 1:
        ans.append(n)
    return ans

# φ関数 : O(n**0.5)
def phi_function(n):
    if n == 1:
        return 0
    
    ans = n
    factor0 = list(set(PrimeFactorize(n))) # nの約数を求める
    # O(log(n)) (nの約数の個数は高々log(n))
    for p in factor0:
        ans *= (p-1)/p
        
    return int(ans)

n = int(input())
print(phi_function(n))

4. NTL_1_E: Euler's Phi Function

# NTL_1_E
# https://www.math.titech.ac.jp/~hoya/Teaching/algebra2022sPDF/extEuc.pdf

# 拡張ユークリッド互除法
def ext_gcd(a,b,x,y,z,w,first=False):
    if a < b:
        tmp = b
        b = a
        a = tmp
        
    q = a//b
    r = a%b
    
    if first:
        x2 = 0
        y2 = 1
        z2 = 1
        w2 = -q
    else:
        x2 = z
        y2 = w
        z2 = x - q*z
        w2 = y - q*w
    
    if r == 0:
        return x2,y2
    
    return ext_gcd(b,r,x2,y2,z2,w2)

a,b = map(int,input().split())

ans = ext_gcd(a,b,x=1,y=1,z=1,w=1,first=True)
if a >= b:
    print(ans[0],ans[1])
else:
    print(ans[1],ans[0])