309874: CF1749D. Counting Arrays

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

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

Output

**题目大意:**
给定一个长度为 $ 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 $ 之后的值。

加入题单

上一题 下一题 算法标签: