{"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$ 的数列 $c,d$ 不同，当且仅当存在整数 $i(1 \\le i \\le L)$，使得 $c_i \\ne d_i$。\n\n## Input\n\n- 第一行一个输入整数 $n$。\n- 第二行输入 $n$ 个整数，表示序列 $a$。\n\n## Output\n\n- 输出一行两个整数。分别表示能得到到的最大 $\\gcd(b_1,b_2,\\cdots,b_n)$ 和对应的不同的 $b$ 的个数，对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\n在解决了上一题之后，琪露诺觉得自己仿佛就是天才。于是，射命丸文又给了她一道简单的数学题。\n\n## Note\n\n### 样例 1 解释\n\n注意到由于 $1\\le b_1\\le a_1=1$，因此 $b_1$ 必须要为 $1$，因此最大的 $\\gcd$ 值只能为 $1$。在这个前提下，所有合法的 $b$ 如下：\n\n- $\\{1,1,1\\},\\{1,1,2\\},\\{1,1,3\\},\\{1,2,1\\},\\{1,2,2\\},\\{1,2,3\\}$。\n\n### 数据范围与约束\n\n对于 $100\\%$ 的数据，$1 \\le n\\le 10^5$，$1 \\le a_i\\le 10^9$。\n\n本题附带一组大样例。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8469","tags":["2022","数论","洛谷原创","O2优化","最大公约数 gcd","组合数学","洛谷月赛"],"sample_group":[["3\n1 2 3","1 6"]],"created_at":"2026-03-03 11:09:25"}}