結果

問題 No.2846 Birthday Cake
コンテスト
ユーザー LyricalMaestro
提出日時 2025-07-27 22:46:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,362 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 95,632 KB
最終ジャッジ日時 2025-07-27 22:46:30
合計ジャッジ時間 7,410 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 31 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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