トップページ -> AOJの解答例 -> NTL_1の解答例

NTL_1の解答例(Python)

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

1. NTL_1_A: Prime Factorize

素因数分解に関する問題です．単純に2からn**0.5+1までの素因数になりうる数字を割ってみています．


# 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

累乗計算に関する問題です． forループでn(最悪で10**9)回計算すると時間がかかるので2乗ごとの塊で計算します．例えば m=3, n=10ならば，(3**2)**5 → ((3**4)**2)*3のような具合です


# 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

オイラーのφ関数に関する問題です．
【外部サイト】オイラーのφ関数 -Wikipedia


# 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

拡張ユークリッド互除法に関する問題です．
以下のPDFが分かりやすいです．コードの計算式は以下のPDFに則っています．
【外部サイト】拡張ユークリッド互除法について


# 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])

【目次に戻る】次へ進む ->