結果

問題 No.1532 Different Products
ユーザー chineristACchineristAC
提出日時 2021-05-02 04:38:30
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,401 bytes
コンパイル時間 496 ms
コンパイル使用メモリ 87,132 KB
実行使用メモリ 101,320 KB
最終ジャッジ日時 2023-09-28 07:48:08
合計ジャッジ時間 23,464 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
79,056 KB
testcase_01 WA -
testcase_02 AC 133 ms
80,120 KB
testcase_03 AC 123 ms
79,248 KB
testcase_04 AC 125 ms
79,048 KB
testcase_05 AC 123 ms
79,144 KB
testcase_06 AC 141 ms
82,396 KB
testcase_07 AC 143 ms
83,200 KB
testcase_08 AC 145 ms
83,008 KB
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 AC 324 ms
85,764 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 WA -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 AC 2,379 ms
96,524 KB
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 AC 121 ms
79,260 KB
testcase_62 AC 121 ms
79,224 KB
testcase_63 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
Dirichlet Product
"""
def mul(N,K,L,data_as,data_ab,data_bs,data_bb):
    data_rs = [0 for i in range(K+1)]
    data_rb = [0 for i in range(L+1)]

    for i in range(1,K+1):
        for j in range(1,K//i+1):
            data_rs[i*j] += data_as[i] * data_bs[j]

    data_as_cum = [data_as[i] for i in range(K+1)]
    data_bs_cum = [data_bs[i] for i in range(K+1)]
    for i in range(1,K+1):
        data_as_cum[i] += data_as_cum[i-1]
        data_bs_cum[i] += data_bs_cum[i-1]

    def cumA(i):
        if 1<=i<=L:
            return data_ab[i]
        else:
            return data_as_cum[(N//i)]

    def cumB(i):
        if 1<=i<=L:
            return data_bb[i]
        else:
            return data_bs_cum[(N//i)]

    for i in range(1,L+1):
        M = int((N//i)**.5)
        for j in range(1,M+1):
            data_rb[i] += data_as[j] * cumB(i*j)
        for j in range(1,M+1):
            data_rb[i] += data_bs[j] * (cumA(i*j)-cumA(N//M))

    return data_rs,data_rb

def single_mul(N,K,L,a,A,val):
    res = [a[i] for i in range(K+1)]
    Res = [A[i] for i in range(L+1)]

    for i in range(1,K+1):
        if i*val<=K:
            res[i*val] += a[i]

    cum = [a[i] for i in range(K+1)]
    for i in range(1,K+1):
        cum[i] += cum[i-1]

    def cumA(i):
        if 1<=i<=L:
            return A[i]
        else:
            return cum[N//i]

    for i in range(1,L+1):
        Res[i] += cumA(i*val)

    return res,Res

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

N,K = mi()

M = 10000
dp = [[0 for j in range(M+1)] for i in range(N+2)]
dp[N+1][1] = 1
for i in range(N,0,-1):
    for j in range(1,M+1):
        dp[i][j] += dp[i+1][j]
        if j*i <= M:
            dp[i][j*i] += dp[i+1][j]

for i in range(1,N+2):
    for j in range(2,M+1):
        dp[i][j] += dp[i][j-1]

stack = [(1,1)]
res = -1
while stack:
    val,L = stack.pop()
    if val<10**5:
        res += 1
        for i in range(L,N+1):
            if val*i <= K:
                if val*i >= 10**5:
                    res += (dp[i+1][K//(val*i)])
                else:
                    stack.append((val*i,i+1))
            else:
                break

print(res%998244353)
0