#P8469. [Aya Round 1 D] 文文的数学游戏

    ID: 7547 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>数论洛谷原创O2优化最大公约数,gcd组合数学洛谷月赛

[Aya Round 1 D] 文文的数学游戏

题目背景

在解决了上一题之后,琪露诺觉得自己仿佛就是天才。于是,射命丸文又给了她一道简单的数学题。

题目描述

给定长度为 nn 的整数序列 aa,你需要构造一个长度为 nn 的整数序列 bb 满足对于所有 1in1\le i\le n,有 1biai1\le b_i \le a_i。且 gcd(b1,b2,,bn)\gcd(b_1,b_2,\cdots,b_n) 最大,其中 gcd\gcd 表示最大公因数。试求出能得到的最大值和取得最大值时,不同的数列 bb 的个数,对 109+710^9+7 取模。

定义两个长度为 LL 的数列 c,dc,d 不同,当且仅当存在整数 i(1iL)i(1 \le i \le L),使得 cidic_i \ne d_i

输入格式

  • 第一行一个输入整数 nn
  • 第二行输入 nn 个整数,表示序列 aa

输出格式

  • 输出一行两个整数。分别表示能得到到的最大 gcd(b1,b2,,bn)\gcd(b_1,b_2,\cdots,b_n) 和对应的不同的 bb 的个数,对 109+710^9+7 取模。
3
1 2 3
1 6

提示

样例 1 解释

注意到由于 1b1a1=11\le b_1\le a_1=1,因此 b1b_1 必须要为 11,因此最大的 gcd\gcd 值只能为 11。在这个前提下,所有合法的 bb 如下:

  • $\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,2,1\},\{1,2,2\},\{1,2,3\}$。

数据范围与约束

对于 100%100\% 的数据,1n1051 \le n\le 10^51ai1091 \le a_i\le 10^9

本题附带一组大样例。