Counting Arrays

题意翻译

给定一个数组 $a$，同时给定一个操作：选取一个数字 $i$，如果 $\gcd(a_i,i) = 1$，我们就可以将**当前**的第 $i$ 位上的数字 $a_i$ 移除掉，而后面的数字会以此补上空缺。 定义一个序列 $b$ 为一个“移除序列”，当且仅当我们可以通过依次选取 $b_1$ 到 $b_n$ 进行上面所说的操作，最终将整个 $a$ 数组移除。 定义一个数组 $a$ 是不好的，当且仅当其有不止一个移除序列。你需要统计出长度为 $[1,n]$ 范围内正整数的，各元素为 $[1,m]$ 范围内正整数的不好的序列的个数，模 $998244353$。

题目描述

Consider an array $ a $ of length $ n $ with elements numbered from $ 1 $ to $ n $ . It is possible to remove the $ i $ -th element of $ a $ if $ gcd(a_i, i) = 1 $ , where $ gcd $ denotes the greatest common divisor. After an element is removed, the elements to the right are shifted to the left by one position. An array $ b $ with $ n $ integers such that $ 1 \le b_i \le n - i + 1 $ is a removal sequence for the array $ a $ if it is possible to remove all elements of $ a $ , if you remove the $ b_1 $ -th element, then the $ b_2 $ -th, ..., then the $ b_n $ -th element. For example, let $ a = [42, 314] $ : - $ [1, 1] $ is a removal sequence: when you remove the $ 1 $ -st element of the array, the condition $ gcd(42, 1) = 1 $ holds, and the array becomes $ [314] $ ; when you remove the $ 1 $ -st element again, the condition $ gcd(314, 1) = 1 $ holds, and the array becomes empty. - $ [2, 1] $ is not a removal sequence: when you try to remove the $ 2 $ -nd element, the condition $ gcd(314, 2) = 1 $ is false. An array is ambiguous if it has at least two removal sequences. For example, the array $ [1, 2, 5] $ is ambiguous: it has removal sequences $ [3, 1, 1] $ and $ [1, 2, 1] $ . The array $ [42, 314] $ is not ambiguous: the only removal sequence it has is $ [1, 1] $ . You are given two integers $ n $ and $ m $ . You have to calculate the number of ambiguous arrays $ a $ such that the length of $ a $ is from $ 1 $ to $ n $ and each $ a_i $ is an integer from $ 1 $ to $ m $ .

输入输出格式

输入格式

The only line of the input contains two integers $ n $ and $ m $ ( $ 2 \le n \le 3 \cdot 10^5 $ ; $ 1 \le m \le 10^{12} $ ).

输出格式

Print one integer — the number of ambiguous arrays $ a $ such that the length of $ a $ is from $ 1 $ to $ n $ and each $ a_i $ is an integer from $ 1 $ to $ m $ . Since the answer can be very large, print it modulo $ 998244353 $ .

输入输出样例

输入样例 #1

2 3

输出样例 #1

6

输入样例 #2

4 2

输出样例 #2

26

输入样例 #3

4 6

输出样例 #3

1494

输入样例 #4

1337 424242424242

输出样例 #4

119112628

**题目大意：**
给定一个长度为 $ n $ 的数组 $ a $，其元素编号从 $ 1 $ 到 $ n $。如果 $ \gcd(a_i, i) = 1 $（其中 $ \gcd $ 表示最大公约数），则可以移除数组的第 $ i $ 个元素。移除一个元素后，右侧的元素会向左移动一个位置。

一个长度为 $ n $ 的数组 $ b $ 是数组 $ a $ 的一个移除序列，如果按照 $ b_1 $ 到 $ b_n $ 的顺序移除，能够将整个数组 $ a $ 清空。例如，对于数组 $ a = [42, 314] $：

- $ [1, 1] $ 是一个移除序列：当你移除数组的第 $ 1 $ 个元素时，满足条件 $ \gcd(42, 1) = 1 $，数组变为 $ [314] $；再次移除第 $ 1 $ 个元素时，满足条件 $ \gcd(314, 1) = 1 $，数组变为空。
- $ [2, 1] $ 不是一个移除序列：尝试移除第 $ 2 $ 个元素时，条件 $ \gcd(314, 2) = 1 $ 不成立。

如果一个数组有至少两个移除序列，则该数组是模糊的。例如，数组 $ [1, 2, 5] $ 是模糊的：它有移除序列 $ [3, 1, 1] $ 和 $ [1, 2, 1] $。数组 $ [42, 314] $ 不是模糊的：它只有一个移除序列 $ [1, 1] $。

给定两个整数 $ n $ 和 $ m $，计算长度为 $ 1 $ 到 $ n $、每个 $ a_i $ 为 $ 1 $ 到 $ m $ 之间的模糊数组 $ a $ 的数量。

**输入输出格式：**
**输入格式：**
输入仅一行，包含两个整数 $ n $ 和 $ m $（$ 2 \le n \le 3 \times 10^5 $；$ 1 \le m \le 10^{12} $）。

**输出格式：**
输出一个整数——长度为 $ 1 $ 到 $ n $、每个 $ a_i $ 为 $ 1 $ 到 $ m $ 之间的模糊数组 $ a $ 的数量。由于答案可能非常大，请输出模 $ 998244353 $ 之后的值。**题目大意：** 给定一个长度为 $ n $ 的数组 $ a $，其元素编号从 $ 1 $ 到 $ n $。如果 $ \gcd(a_i, i) = 1 $（其中 $ \gcd $ 表示最大公约数），则可以移除数组的第 $ i $ 个元素。移除一个元素后，右侧的元素会向左移动一个位置。 一个长度为 $ n $ 的数组 $ b $ 是数组 $ a $ 的一个移除序列，如果按照 $ b_1 $ 到 $ b_n $ 的顺序移除，能够将整个数组 $ a $ 清空。例如，对于数组 $ a = [42, 314] $： - $ [1, 1] $ 是一个移除序列：当你移除数组的第 $ 1 $ 个元素时，满足条件 $ \gcd(42, 1) = 1 $，数组变为 $ [314] $；再次移除第 $ 1 $ 个元素时，满足条件 $ \gcd(314, 1) = 1 $，数组变为空。 - $ [2, 1] $ 不是一个移除序列：尝试移除第 $ 2 $ 个元素时，条件 $ \gcd(314, 2) = 1 $ 不成立。 如果一个数组有至少两个移除序列，则该数组是模糊的。例如，数组 $ [1, 2, 5] $ 是模糊的：它有移除序列 $ [3, 1, 1] $ 和 $ [1, 2, 1] $。数组 $ [42, 314] $ 不是模糊的：它只有一个移除序列 $ [1, 1] $。 给定两个整数 $ n $ 和 $ m $，计算长度为 $ 1 $ 到 $ n $、每个 $ a_i $ 为 $ 1 $ 到 $ m $ 之间的模糊数组 $ a $ 的数量。 **输入输出格式：** **输入格式：** 输入仅一行，包含两个整数 $ n $ 和 $ m $（$ 2 \le n \le 3 \times 10^5 $；$ 1 \le m \le 10^{12} $）。 **输出格式：** 输出一个整数——长度为 $ 1 $ 到 $ n $、每个 $ a_i $ 为 $ 1 $ 到 $ m $ 之间的模糊数组 $ a $ 的数量。由于答案可能非常大，请输出模 $ 998244353 $ 之后的值。