K-同学聚会_第十一届"图灵杯"NEUQ-ACM程序设计竞赛

同学聚会

比赛主页

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

有n名同学，他们的开心值为 $a[0],a[1]…a[n-1]$ 。现在从中随机选取一个区间的同学进行聚会。对于一个区间 $[l,r](l \leq r)$ 的同学，大家在一块聚会后，每个人的开心值就会同时变为 $gcd(a[l],a[l+1]…a[r])$ ，本次的聚会的开心值即为所有参加聚会的同学的开心值之和。请你求出这次聚会的开心值的期望，并 $mod ~998244353$ 输出。

输入描述:

第一行输入一个 $n$ , $1 \leq n \leq 2 \times 10^5$ ，表示同学总数\

第二行输入n个整数 $a_0,a_1,a_2,...,a_{n-1}$ ，表示n名同学的各自的开心值（ $1 \leq a_i \leq 2 \times 10^5$ ）

输出描述:

输出一个整数 $ans$ ，表示这次聚会的开心值的期望

可以证明，答案总是一个有理数,将其化为不可约分数 $p/q$ 后，在 $[0,998244353)$ 中存在唯一整数 $ans$ 满足 $ans \times q ≡ p$ ，输出 $ans$ 即可

示例1

输入

复制

3
2 6 3

输出

复制

说明

第一个样例：

选择第 $1$ 位同学进行聚会,开心值为 $2$

选择第 $2$ 名同学进行聚会，开心值为 $6$

选择第 $3$ 名同学进行聚会，开心值为 $3$

选择第 $1、2$ 名同学进行聚会，两个人的开心值都变为 $gcd(2,6)=2$ ，总开心值为 $2+2=4$

选择第 $2、3$ 名同学进行聚会，两个人的开心值都变为 $gcd(6,3)=3$ ，总开心值为 $3+3=6$

选择第1、2、3名同学进行聚会，三个人的开心值都变为 $gcd(2,6,3)=1$ ，总开心值为 $1+1+1=3$

随机选择一种聚会的总开心值为 $(2 + 6 + 3 + 4 + 6 + 3) / 6 = 4$

示例2

输入

复制

3
3 1 4

输出

复制

499122179

说明

答案为 $15/6$ , $499122179 \times 6 ≡ 15(mod~998244353)$ ，输出 $499122179$ 即可