Modular Stability

题意翻译

## 题目描述 求有多少个长度为 $k$ 的序列 $a$，满足以下条件： - $\forall 1 \le i < k,a_i < a_{i+1}$ - $\forall 1 \le i \le k,1 \le a_i \le n$ - 对于任意一个 $1$ 至 $k$ 的排列 $p$，满足 $( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) = ((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3} \bmod \cdots \bmod a_{p_k}$。其中 $x$ 为任意非负整数。 结果对 $998,244,353$ 取模。 ## 输入格式 输入一行两个整数 $n,k$，意义如题目描述所示。 ## 输出格式 输出一个整数表示答案。 ## 说明/提示 $1 \le n,k \le 5 \times 10^5$。

题目描述

We define $ x \bmod y $ as the remainder of division of $ x $ by $ y $ ( $ \% $ operator in C++ or Java, mod operator in Pascal). Let's call an array of positive integers $ [a_1, a_2, \dots, a_k] $ stable if for every permutation $ p $ of integers from $ 1 $ to $ k $ , and for every non-negative integer $ x $ , the following condition is met: $ (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k} $ That is, for each non-negative integer $ x $ , the value of $ (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k $ does not change if we reorder the elements of the array $ a $ . For two given integers $ n $ and $ k $ , calculate the number of stable arrays $ [a_1, a_2, \dots, a_k] $ such that $ 1 \le a_1 < a_2 < \dots < a_k \le n $ .

输入输出格式

输入格式

The only line contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 5 \cdot 10^5 $ ).

输出格式

Print one integer — the number of stable arrays $ [a_1, a_2, \dots, a_k] $ such that $ 1 \le a_1 < a_2 < \dots < a_k \le n $ . Since the answer may be large, print it modulo $ 998244353 $ .

输入输出样例

输入样例 #1

7 3

输出样例 #1

16

输入样例 #2

3 7

输出样例 #2

0

输入样例 #3

1337 42

输出样例 #3

95147305

输入样例 #4

1 1

输出样例 #4

1

输入样例 #5

500000 1

输出样例 #5

500000

题意翻译

## 题目描述 求有多少个长度为 $k$ 的序列 $a$，满足以下条件： - $\forall 1 \le i < k,a_i < a_{i+1}$ - $\forall 1 \le i \le k,1 \le a_i \le n$ - 对于任意一个 $1$ 至 $k$ 的排列 $p$，满足 $( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) = ((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3} \bmod \cdots \bmod a_{p_k}$。其中 $x$ 为任意非负整数。 结果对 $998,244,353$ 取模。 ## 输入格式 输入一行两个整数 $n,k$，意义如题目描述所示。 ## 输出格式 输出一个整数表示答案。 ## 说明/提示 $1 \le n,k \le 5 \times 10^5$。