[Baekjoon] 7806. GCD! [G4]

📚 質問する
https://www.acmicpc.net/problem/7806
nとkは10億で,直接ユークリッドアーク除去法で探すとタイムアウトが発生する.
だからkを素数nに分解!ekと同じ素数が何回現れるかを探し出す.
素数を分解する方法は平方根以下の素数を探し,素数を繰り返し探す方法である.少数と少数の個数を一緒にするためにディックシャーナを用いた.
素数を分解すると、平方根より大きい素数が存在する可能性があります.この可能性を常にチェックすることがポイントです.
kを素数に分解した時が2^3 * 3^2だったら、n!2はいくつか、3はいくつかを把握し、最大公約数を求める.
n!中xの数を特定する方法はn!//n!//xが0になるまで繰り返し、結果値を加算します.
小さな箱を上の考えで解きましょう.
4!第30課です.
まず30を素数に分解します.では、2 * 3 * 5です.
4!4!//2を繰り返します.
4!//2=12、12/2=6、6/2=3、3/2=1=>を合わせた22は合計2の個数である.
22個と1個のうち、最も高価な1個に最大公約数を乗じた2個.
上のように、3と5も最大公約数を乗じた個数を繰り返し見つけます.
入力された個数が不定であるため、try: except: breakを用いて終了する.
📒 コード#コード#

while True:
    try:
        n, k = map(int, input().split())    # 입력제한이 없는 경우 try except로 해결
    except:
        break
    temp = k                    # k를 소인수분해 계산하기 위해 temp에 담는다. 
    smalls = {}                 # 소인수와 소인수의 개수를 담기 위해 딕셔너리 사용
    for i in range(2, k+1):     # k의 소인수 분해
        if i * i > k:           # 제곱근보다 클 경우 종료
            break
        while temp % i == 0:    # 소인수일 경우 개수만큼 담아준다.
            temp //= i
            if smalls.get(i):
                smalls[i] += 1    # k의 소인수와 갯수를 담기 위해 list로 담는다.
            else:
                smalls[i] = 1
    if temp != 1:               # 제곱근보다 큰 소인수 추가
        smalls[temp] = 1         # k의 소인수가 아직 덜 나왔을 때 추가

    result = 1
    for num, cnt in smalls.items():
        temp = n
        cnt2 = 0                # 소인수가 n!에 곱해진 개수
        while temp // num:
            temp //= num
            cnt2 += temp
            if cnt2 >= cnt:     # n!에 존재하는 소인수의 개수가 k의 개수보다 크거나 같으면 종료한다.
                break           # 더 파악할 필요가 없다.

        result *= num ** min(cnt, cnt2) # n!에 존재하는 소인수의 개수와, k의 소인수 개수 중 최소값을 소인수에 거듭제곱해 곱해준다.
    print(result)

🔍 結果