#P8469. [Aya Round 1 D] 文文的数学游戏
[Aya Round 1 D] 文文的数学游戏
题目背景
在解决了上一题之后,琪露诺觉得自己仿佛就是天才。于是,射命丸文又给了她一道简单的数学题。
题目描述
给定长度为 的整数序列 ,你需要构造一个长度为 的整数序列 满足对于所有 ,有 。且 最大,其中 表示最大公因数。试求出能得到的最大值和取得最大值时,不同的数列 的个数,对 取模。
定义两个长度为 的数列 不同,当且仅当存在整数 ,使得 。
输入格式
- 第一行一个输入整数 。
- 第二行输入 个整数,表示序列 。
输出格式
- 输出一行两个整数。分别表示能得到到的最大 和对应的不同的 的个数,对 取模。
3
1 2 3
1 6
提示
样例 1 解释
注意到由于 ,因此 必须要为 ,因此最大的 值只能为 。在这个前提下,所有合法的 如下:
- $\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,2,1\},\{1,2,2\},\{1,2,3\}$。
数据范围与约束
对于 的数据,,。
本题附带一组大样例。