Description：

给出一个序列 $a$ ，对于集合 $S$ ，定义 $f(S)=\max_{i,j\in S,i\ne j}\gcd(a_i,a_𝑗)$ ，求： $$ \sum_{l\leqslant r}f([1,l]\cup[r,n]) $$ $1\leqslant n,a_i\leqslant 50000$

Solution：

我们从右往左枚举 $r$ ，每次当插入一个新的 $r$ ，我们都暴力遍历它的所有约数，先预处理一个 $p[i]$ 表示 $i$ 这个数第一次作为某个数的约数出现的时候，然后显然 $l\in[p[i],r)$ 都可以以 $i$ 为 $\gcd$ ，于是就用吉司机线段树区间取 $\max$ ，然后做完后再区间求和就行了。

Code：