Problem:


Score : 600 points

Problem Statement

Find the number of sequences of length K consisting of positive integers such that the product of any two adjacent elements is at most N, modulo 10^9+7.

Constraints

1\leq N\leq 10^9

1 2\leq K\leq 100 (fixed at 21:33 JST)

N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of sequences, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

5

(1,1), (1,2), (1,3), (2,1), and (3,1) satisfy the condition.

Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712



Sample input:
3 2


Sample output:
5

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    for i in d.keys():
        if d[i] != 2:
            print("No")
            quit()
    print("Yes")
    return

#B
def B():
    n = I()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        k = p[i-1:i+2]
        k.sort()
        if k[1] == p[i]:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    d = LI()
    d.sort()
    print(d[n//2]-d[n//2-1])
    return

#D
def D():
    n,k = LI()
    fact = [1]*100001
    for i in range(1,100001):
        fact[i] = fact[i-1]*i%mod
    inv = [1]*100001
    inv[-1] = pow(fact[-1],mod-2,mod)
    for i in range(1,100001)[::-1]:
        inv[i-1] = inv[i]*i%mod

    for i in range(1,k+1):
        if n-k+1 < i:
            print(0)
        else:
            ans = fact[n-k+1]*inv[i]*inv[n-k+1-i]%mod
            ans *= fact[k-1]*inv[k-i]*inv[i-1]%mod
            ans %= mod
            print(ans)
    return

#E
def E():
    ma = 100000000
    def dijkstra(s):
        d = defaultdict(lambda : ma)
        q = [(0,s,0)]
        d[(s,0)] = 0
        while q:
            dx,x,t = heappop(q)
            t = (t+1)%3
            k = t == 1
            for y in v[x]:
                if dx+k < d[(y,t)]:
                    d[(y,t)] = dx+k
                    heappush(q,(d[(y,t)],y,t))
        res = d[(g,0)]
        if res == ma:
            res = -1
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    s,g = LI()
    s -= 1
    g -= 1
    print(dijkstra(s))
    return

#F
def F():
    n,k = LI()
    MA = math.ceil(n**0.5)
    MA2 = 2*MA
    f = [n//i if i > 0 else 0 for i in range(MA+1)]
    if f[MA] <= MA:
        MA2 -= 1
    if f[MA-1] <= MA-1:
        MA2 -= 1
    dp = [[0]*(MA2) for i in range(k)]
    for i in range(MA+1):
        dp[0][i] = 1
    j = MA2-1
    for i in range(1,MA):
        dp[0][j] = f[i]-f[i+1]
        j -= 1
    dp[0][0] = 0
    if f[MA] < MA:
        MA -= 1
    s = [dp[0][i] for i in range(MA2)]
    for i in range(MA2-1):
        dp[0][i+1] += dp[0][i]
        dp[0][i+1] %= mod
    for l in range(k-1):
        for i in range(1,MA2):
            j = MA2-i
            dp[l+1][i] = dp[l][j]*s[i]
            dp[l+1][i] %= mod
            dp[l+1][i] += dp[l+1][i-1]
            dp[l+1][i] %= mod
    print(dp[-1][-1])
    return


#Solve
if __name__ == "__main__":
    F()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dp = [[0]*N for i in range(K)]
for i in range(N):
    dp[0][i] = 1
for i in range(K-1):
    for j in range(N):
        for k in range(N//(j+1)):
            dp[i+1][j] += dp[i][k]

ans=0
for i in range(N):
    ans += dp[K-1][i]
ans = ans % 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dp = [[0]*N for i in range(K)]
for i in range(N):
    dp[0][i] = 1
for i in range(K-1):
    for j in range(N):
        for k in range(N//(j+1)):
            dp[i+1][j] += dp[i][k]

ans=0
for i in range(N):
    ans += dp[K-1][i]
print(ans//(1e9 + 7))

Submission status: Runtime Error

Solution code:
import math
import copy
N, K = map(int, (input().split()))

mod = 10**9 + 7

ans_array = []
divide_max = N
for i in range(2, math.floor(math.sqrt(N)) + 1):
    divide = math.floor(N / i)
    ans_array.append(divide_max - divide)
    divide_max = divide

for i in range(divide):
    ans_array.append(1)
ans_array = ans_array[::-1]
ans_count = copy.deepcopy(ans_array)
# print(ans_count)
ans_length = len(ans_array)
ans_acc = [0] * ans_length

for k in range(2, K + 1):
    ans_acc[0] = ans_array[0]
    for i in range(1, ans_length):
        ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod
    # print(ans_array)
    # print(ans_acc)
    for i in range(ans_length):
        ans_array[i] = ans_acc[ans_length-i-1] * ans_count[i] % mod

ans_acc[0] = ans_array[0]
for i in range(1, ans_length):
    ans_acc[i] = (ans_acc[i - 1] + ans_array[i]) % mod

print(ans_acc[-1])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

from itertools import product

ans = 0
for X in product(range(1,n+1), repeat=k):
#    _ans = [1 if X[i]*X[i+1] > n else 0 for i in range(k-1)]
#    if sum(_ans) == 0:
    ans += 1
    for i in range(k-1):
        if X[i]*X[i+1] > n:
            ans -= 1
            break

print(ans % (10**9+7))