結果

問題 No.1532 Different Products
ユーザー LyricalMaestro
提出日時 2025-05-04 10:38:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 973 ms / 4,000 ms
コード長 1,172 bytes
コンパイル時間 651 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 136,936 KB
最終ジャッジ日時 2025-05-04 10:38:43
合計ジャッジ時間 37,035 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

import math

def solve_simple(N, K):
    dp = [0] * (K + 1)

    dp[1] = 1
    for j in range(1, N + 1):
        new_dp = dp.copy()

        for k in range(K + 1):
            new_k = k * j
            if new_k <= K:
                new_dp[new_k] += dp[k]
        dp = new_dp
    
    print(sum(dp) - 1)



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

    if K <= 10:
        solve_simple(N, K)
        return

    sqrt_k = int(math.sqrt(K))

    dp = [0] * (sqrt_k + 1)
    dp2 = [0] * (sqrt_k + 1)
    dp[1] = 1
    for j in range(1, N + 1):
        new_dp = dp.copy()
        new_dp2 = dp2.copy()

        for k in range(sqrt_k + 1):
            new_k = j * k
            if new_k <= sqrt_k:
                new_dp[new_k] += dp[k]
            else:
                l = K // new_k
                new_dp2[l] += dp[k]
        
        for k in range(sqrt_k + 1):
            new_k2 = k // j
            if new_k2 > 0:
                new_dp2[new_k2] += dp2[k]
        
        dp = new_dp
        dp2 = new_dp2
    
    answer = sum(dp) - 1
    answer += sum(dp2)

    print(answer)




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