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

Luogu

IDLGP8469

Time2000ms

Memory512MB

DifficultyP2

2022数论洛谷原创O2优化最大公约数 gcd组合数学洛谷月赛

给定长度为 $n$ 的整数序列 $a$，你需要构造一个长度为 $n$ 的整数序列 $b$ 满足对于所有 $1\le i\le n$，有 $1\le b_i \le a_i$。且 $\gcd(b_1,b_2,\cdots,b_n)$ 最大，其中 $\gcd$ 表示最大公因数。试求出能得到的最大值和取得最大值时，不同的数列 $b$ 的个数，对 $10^9+7$ 取模。定义两个长度为 $L$ 的数列 $c,d$ 不同，当且仅当存在整数 $i(1 \le i \le L)$，使得 $c_i \ne d_i$。 ## Input - 第一行一个输入整数 $n$。 - 第二行输入 $n$ 个整数，表示序列 $a$。 ## Output - 输出一行两个整数。分别表示能得到到的最大 $\gcd(b_1,b_2,\cdots,b_n)$ 和对应的不同的 $b$ 的个数，对 $10^9+7$ 取模。 [samples] ## Background 在解决了上一题之后，琪露诺觉得自己仿佛就是天才。于是，射命丸文又给了她一道简单的数学题。 ## Note ### 样例 1 解释注意到由于 $1\le b_1\le a_1=1$，因此 $b_1$ 必须要为 $1$，因此最大的 $\gcd$ 值只能为 $1$。在这个前提下，所有合法的 $b$ 如下： - $\{1,1,1\},\{1,1,2\},\{1,1,3\},\{1,2,1\},\{1,2,2\},\{1,2,3\}$。 ### 数据范围与约束对于 $100\%$ 的数据，$1 \le n\le 10^5$，$1 \le a_i\le 10^9$。本题附带一组大样例。

Samples

Input #1

3
1 2 3

Output #1

1 6

API Response (JSON)

{
  "problem": {
    "name": "[Aya Round 1 D] 文文的数学游戏",
    "description": {
      "content": "给定长度为 $n$ 的整数序列 $a$，你需要构造一个长度为 $n$ 的整数序列 $b$ 满足对于所有 $1\\le i\\le n$，有 $1\\le b_i \\le a_i$。且 $\\gcd(b_1,b_2,\\cdots,b_n)$ 最大，其中 $\\gcd$ 表示最大公因数。试求出能得到的最大值和取得最大值时，不同的数列 $b$ 的个数，对 $10^9+7$ 取模。 定义两个长度为 $L$ 的数列",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8469"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定长度为 $n$ 的整数序列 $a$，你需要构造一个长度为 $n$ 的整数序列 $b$ 满足对于所有 $1\\le i\\le n$，有 $1\\le b_i \\le a_i$。且 $\\gcd(b_1,b_2,\\cdots,b_n)$ 最大，其中 $\\gcd$ 表示最大公因数。试求出能得到的最大值和取得最大值时，不同的数列 $b$ 的个数，对 $10^9+7$ 取模。\n\n定义两个长度为 $L$ 的数列...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments