#1538. 「florr IO Round 1」数字游戏

「florr IO Round 1」数字游戏

题目描述

给出一个正整数 nn 以及正整数序列 aa,其中 nn 表示序列 aa 的长度。

我们定义一个区间 [l,r][l,r] 的权值为 f(l,r)f(l,r),其中:

$$f(l,r)=\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [\gcd(b_1,b_2,b_3,\dots,b_{r-l+1})=1]$$

求所有区间的权值之和,即求:

∑l=1n∑r=lnf(l,r)\sum^{n}_{l=1} \sum^{n}_{r=l} f(l,r)

答案对 998244353998244353 取模。

输入格式

第一行,一个整数 nn。

第二行,nn 个数表示的序列 aa。

输出格式

共 11 行,表示答案。

样例

2
1 2
4
5
2 4 4 5 4 
1301
10
1 7 5 5 7 6 9 2 4 8 
10816520

题目来源:洛谷 P14009