区间最大公约数之和

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$。

对于一个区间 $[l,r]$，定义

请你求出所有非空连续区间的最大公约数之和：

答案可能超过 $64$ 位有符号整数范围，使用 C++ 时建议用 __int128 保存答案。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示所有非空连续区间的最大公约数之和。答案不取模。

样例 1

3
2 4 6

18

六个非空连续区间的最大公约数分别为 $2,4,6,2,2,2$，因此答案为 $18$。

样例 2

见下发文件：gcd2.in 与 gcd2.out。

数据范围

对于 $100\%$ 的数据，$1\le n\le2\times10^5$，$1\le a_i\le10^9$。

更多样例

以下 2 组样例取自原题附件：

• gcd-down1.in / gcd-down1.out
• gcd-down2.in / gcd-down2.out