#1180036 (Python3) No.3651 K-th Sum of Divisors

• 問題: No.3651 K-th Sum of Divisors
• ユーザー: Phenanthrene86
• 提出日時: 2026-08-28 22:38:32
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: WA
• 実行時間: -
• コード長: 4,400 bytes
• コンパイル時間: 310 ms
• コンパイル使用メモリ: 21,540 KB
• 実行使用メモリ: 20,732 KB
• 最終ジャッジ日時: 2026-08-28 22:38:46
• 合計ジャッジ時間: 11,074 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 25 WA * 30

ソースコード

import random
import math
from typing import Dict, List

def mi():
    return map(int, input().split())

def miller_rabin(n: int) -> bool:
    """
    説明:
        64-bit 整数に対して確定的に使える Miller-Rabin 素数判定。
    計算量:
        O(log^3 n) 程度。実用上は非常に高速。
    使用方法:
        ok = miller_rabin(10**18 + 3)
    """
    if n < 2:
        return False
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    for p in small_primes:
        if n == p:
            return True
        if n % p == 0:
            return False
    d = n - 1
    s = 0
    while d & 1 == 0:
        s += 1
        d >>= 1
    for a in (2, 325, 9375, 28178, 450775, 9780504, 1795265022):
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

def _pollard_rho_one(n: int) -> int:
    """
    説明:
        Pollard Rho の Brent 風反復で n の非自明な因数を 1 つ返す内部関数。
    計算量:
        期待 O(n^{1/4}) 程度
    使用方法:
        d = _pollard_rho_one(n)
    """
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    while True:
        c = random.randrange(1, n - 1)
        y = random.randrange(0, n - 1)
        m = 128
        g = 1
        r = 1
        q = 1
        x = 0
        ys = 0
        while g == 1:
            x = y
            for _ in range(r):
                y = (y * y + c) % n
            k = 0
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r - k)):
                    y = (y * y + c) % n
                    q = q * abs(x - y) % n
                g = math.gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = (ys * ys + c) % n
                g = math.gcd(abs(x - ys), n)
        if 1 < g < n:
            return g

def pollard_rho_factor(n: int) -> Dict[int, int]:
    """
    説明:
        Pollard Rho と Miller-Rabin により n を完全素因数分解し、{素因数: 指数} を返す。
    計算量:
        期待 O(n^{1/4} log n) 程度
    使用方法:
        fac = pollard_rho_factor(10**18 + 9)
    """
    res: Dict[int, int] = {}

    def rec(x: int) -> None:
        """
        説明:
            pollard_rho_factor 内部で x を再帰的に素因数分解する。
        計算量:
            Pollard Rho の期待計算量に従う。
        使用方法:
            rec(x)
        """
        if x == 1:
            return
        if miller_rabin(x):
            res[x] = res.get(x, 0) + 1
            return
        d = _pollard_rho_one(x)
        rec(d)
        rec(x // d)
    if n < 2:
        return {}
    rec(n)
    return dict(sorted(res.items()))

def make_divisors_from_factor(fac: Dict[int, int]) -> List[int]:
    """
    説明:
        素因数分解辞書 {p: e} から全約数を昇順で列挙する。
    計算量:
        約数個数を d として O(d log d)
    使用方法:
        divs = make_divisors_from_factor({2: 2, 3: 1})
    """
    divs = [1]
    for p, e in fac.items():
        old = divs
        new: List[int] = []
        pe = 1
        for _ in range(e + 1):
            for d in old:
                new.append(d * pe)
            pe *= p
        divs = new
    divs.sort()
    return divs

def div_factor_large(n: int) -> List[int]:
    """
    説明:
        Pollard Rho による素因数分解を使い、limit に依存せず n の約数を列挙する。
    計算量:
        素因数分解の期待時間 + 約数個数を d として O(d log d)
    使用方法:
        divs = div_factor_large(10**12 + 39)
    """
    return make_divisors_from_factor(pollard_rho_factor(n))

n, k = mi()
a = [n]
s =set()
cycle_len = 0
if k == 1:
    print(a[-1])
    exit()
for i in range(10000000):
    a.append(sum(div_factor_large(a[-1])) % 100003)
    if i + 1 == k:
        print(a[-2])
        exit()
    if a[-1] not in s:
        s.add(a[-1])
    else:
        break
    
for i in range(len(a)):
    if a[i] == a[-1]:
        id = i
        break
cycle_len = len(a) - 1 - id
print(a[id + (k - id) % cycle_len])