結果

問題 No.2846 Birthday Cake
コンテスト
ユーザー LyricalMaestro
提出日時 2025-07-27 22:46:11
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,852 ms / 2,000 ms
+ 840µs
コード長 1,362 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 96,332 KB
最終ジャッジ日時 2026-07-13 14:47:49
合計ジャッジ時間 14,846 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2846

def calc_gcd(A, B):
    """
    正の整数A, Bの最大公約数を計算する
    """
    a = max(A, B)
    b = min(A, B)
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b

def main():
    K, N = map(int, input().split())

    total = 1
    for n in range(2, N + 1):
        gcd = calc_gcd(total, n)
        total = (total // gcd) * n

    candidates = []
    for i in range(1 , N + 1):
        candidates.append(total // i)


    # 取り分
    def dfs(N, K, candidates, total, index, xxx, c):
        if total == 0 and K == 0:
            return c
        elif total == 0 and K > 0:
            return 0
        elif total > 0 and K == 0:
            return 0
        
        if total < candidates[-1] * K:
            return 0
        
        if total > candidates[index] * K:
            return 0
        
        ans = 0        
        for ind in range(index, len(candidates)):
            if total - candidates[ind] < 0:
                continue
            
            xxx[ind] += 1
            ans += dfs(N, K - 1, candidates, total - candidates[ind],  ind, xxx, (c * K) // xxx[ind])
            xxx[ind] -= 1
        return ans
    xxx = [0] * len(candidates)
    answer = dfs(N, K, candidates, total, 0, xxx, 1)
    print(answer)




if __name__ == "__main__":
    main()
0