众所周知，在算法竞赛中，出题人对他出的题的难度往往存在错误的估计，比如出题人本想出个中等题，没想到却出成了简单题；本想出个自闭题，结果数据太水变成了签到题，因此，为了让一场比赛能有良好的体验，有一个靠谱的验题人是非常重要的， CC出好题目后，便拿给小马哥看，不出所料，这些题目小马哥全都是看一眼就会做了，而且，小马哥觉得这些题对于参赛选手来说也太水了（5个签到题哦～），为了避免发生全场十几个队AK
众所周知，在算法竞赛中，出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个中等题，没想到却出成了简单题；本想出个自闭题，结果数据太水变成了签到题。因此，为了让一场比赛能有良好的体验，有一个靠谱的验题人是非常重要的。 CC出好题目后，便拿给小马哥看。不出所料，这些题目小马哥全都是看一眼就会做了。而且，小马哥觉得这些题对于参赛选手来说也太水了（5个签到题哦～）。为了避免发生全场十几个队AK这种紧急事态，小马哥决定把一道签到题改成简单题，于是便有了现在这个题目。 小马哥非常喜欢数论，尤其钟爱“最大公约数”（Greatest Common Divisor，简称GCD）这一概念，因此他打算出一道和GCD有关的题目。小马哥首先给出了含n个正整数的序列a1,a2,⋯ ,ana_1, a_2, cdots , a_na1,a2,⋯,an，然后让你考虑该序列的所有子区间的数对应的GCD值，也就是说考虑所有gcd(al,⋯ ,ar)gcd (a_l, cdots, a_r)gcd(al,⋯,ar)的值。显然，这样的值一共有n(n+1)2dfrac{n(n+1)}{2}2n(n+1)个。一个中二出题人可能会让你求这n(n+1)2dfrac{n(n+1)}{2}2n(n+1)数中第k大的数，但幸运的是，小马哥是个正经出题人，因此它只让你求这n(n+1)2dfrac{n(n+1)}{2}2n(n+1)个数之和模109+710^9+7109+7的结果。 也就是要求下面这个式子： ans=(∑l=1n∑r=lngcd(al,⋯ ,ar)) mod (109+7)ans = (sum_{l=1}^{n} sum_{r=l}^{n} gcd(a_l, cdots, a_r)) bmod (10^9+7)ans=(∑l=1n∑r=lngcd(al,⋯,ar))mod(109+7) 小马哥在此预祝大家AK～
