만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

좋은 배열

시간 제한2초메모리 제한1024 MB

요약
길이가 n이고 원소가 c 이하인 배열 중 각 원소가 바로 다음 원소로 나누어떨어지는 배열의 개수를 998244353으로 나눈 나머지로 구합니다.
난이도

보통10점 중 6점

유형
정수론, 조합론, 수학
정답자
아직 제출이 없습니다

문제

최근 Vasya는 정수 나눗셈을 배웠다. 이 신성한 지식에 영감을 받아, 그는 나눗셈 조건을 만족하는 양의 정수 배열을 더 알아보기로 했다. 정확히는, 11부터 n−1n-1까지의 모든 ii에 대해 aia_i가 ai+1a_{i+1}로 나누어떨어지면 배열 a={a1,a2,…,an}a=\{a_1,a_2,\ldots,a_n\}을 좋은 배열이라고 부른다. cc 이하의 정수로 이루어진 길이 nn인 좋은 배열의 개수를 구하라.

입력

첫 줄에 두 정수 nn과 cc가 주어진다 (1≤n,c≤5⋅1071 \le n, c \le 5 \cdot 10^7). nn은 배열의 길이이고, cc는 허용되는 최댓값이다.

출력

길이가 nn이고 cc 이하의 양의 정수로 이루어진 좋은 배열의 개수를 정수 하나로 출력한다. 이 수는 매우 클 수 있으므로 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    3 3
    
    예상 출력
    7
    
  2. 예제 2

    입력
    2 6
    
    예상 출력
    14