Best Divisor

アルゴリズム概要

問題説明

Kristenは数字の各桁の和（桁和）で数の良し悪しを判定します。与えられた整数 n の約数のうち、以下の基準で「最良」のものを見つけてください：

1. 桁和が最大の約数を選ぶ（例：6の桁和は6、12の桁和は1+2=3なので6が優先）
2. 桁和が同じ場合は値が小さい方を選ぶ

入出力例

12

6

制約条件

• 1 ≤ n ≤ 10⁵

戦略

1. 効率的な約数列挙: √n まで探索し、i が約数なら i と n/i の両方を収集
2. 桁和計算: 各約数を文字列化し、各桁を合計
3. 最良選択: (桁和が最大, 値が最小) の優先順位で比較

主要ポイント

• 時間計算量: O(√n + d·log n) - √n までのループ + 各約数の桁和計算 O(log n)
• 空間計算量: O(d) - 約数リストの保存
• 最適化: Pythonの組み込み関数 max() と sum() を活用

ステップバイステップ解説

Python実装

def findBestDivisor(n: int) -> int:
    """
    最良の約数を見つける（競技プログラミング最適化版）

    Time Complexity: O(√n)
    Space Complexity: O(d) where d is number of divisors
    """
    divisors = []
    i = 1

    # √n まで探索して約数をペアで収集
    while i * i <= n:
        if n % i == 0:
            divisors.append(i)
            # 平方数でない場合のみペアを追加
            if i != n // i:
                divisors.append(n // i)
        i += 1

    # 桁和が最大、同値なら最小値を選択
    # タプル比較: (桁和大, 値小) = (sum, -divisor)
    return max(divisors, key=lambda x: (sum(int(d) for d in str(x)), -x))


# 使用例
if __name__ == '__main__':
    n = int(input().strip())
    result = findBestDivisor(n)
    print(result)

フローチャート

フローの説明：
1. 入力 n を受け取り、空の約数リスト divisors と i=1 で初期化
2. i×i ≤ n の間ループ：n を i で割り切れるか判定
3. 割り切れる場合、i と n//i を約数リストに追加（i≠n//i の場合のみペア追加）
4. i を1増やしてループ継続
5. ループ終了後、約数リストから桁和が最大（同値なら最小値）の約数を選択
6. 結果を返して終了

計算量分析

最適化ポイント

• √n探索: 約数は必ずペア (i, n/i) で出現するため、√n まで調べれば全約数が得られる
• Python組み込み関数: max() のkey引数で、タプル比較 (桁和, -値) により1パスで最良約数を選択
• 桁和計算: sum(int(d) for d in str(x)) でジェネレータ式とC実装のsumを活用
• 平方数対策: i != n // i で重複を防ぐ（例：n=16 の場合 i=4 を2回追加しない）

具体例での計算量