2019年华南理工大学程序设计竞赛（春季赛）H Parco_Love_GCD （思维 + 数论 + 前缀和）

链接：https://ac.nowcoder.com/acm/contest/625/H

来源：牛客网

Parco_Love_GCD

时间限制：C/C++ 3秒，其他语言6秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

众所周知，在算法竞赛中，出题人对他出的题的难度往往存在错误的估计。比如出题人本想出个中等题，没想到却出成了简单题；本想出个自闭题，结果数据太水变成了签到题。因此，为了让一场比赛能有良好的体验，有一个靠谱的验题人是非常重要的。

CC出好题目后，便拿给小马哥看。不出所料，这些题目小马哥全都是看一眼就会做了。而且，小马哥觉得这些题对于参赛选手来说也太水了（5个签到题哦～）。为了避免发生全场十几个队AK这种紧急事态，小马哥决定把一道签到题改成简单题，于是便有了现在这个题目。

小马哥非常喜欢数论，尤其钟爱“最大公约数”（Greatest Common Divisor，简称GCD）这一概念，因此他打算出一道和GCD有关的题目。小马哥首先给出了含n个正整数的序列a1,a2,⋯,ana1,a2,⋯,an，然后让你考虑该序列的所有子区间的数对应的GCD值，也就是说考虑所有gcd(al,⋯,ar)gcd(al,⋯,ar)的值。显然，这样的值一共有n(n+1)2n(n+1)2个。一个中二出题人可能会让你求这n(n+1)2n(n+1)2数中第k大的数，但幸运的是，小马哥是个正经出题人，因此它只让你求这n(n+1)2n(n+1)2个数之和模109+7109+7的结果。

也就是要求下面这个式子：

ans=(∑nl=1∑nr=lgcd(al,⋯,ar))mod(109+7)ans=(∑l=1n∑r=lngcd(al,⋯,ar))mod(109+7)

小马哥在此预祝大家AK～

输入描述:

第一行是一个整数n (1≤n≤5×105)n (1≤n≤5×105)，表示数的个数。

接下来一行给出n个整数，其中第i个整数aiai满足1≤ai≤1091≤ai≤109。      

输出描述:

输出一行一个整数，表示ans的值。      

示例1

输入

复制

5
16 4 7 21 3      

输出

复制

72      

这是一个套路题，我们要先知道，求gcd，对于任意两个数，最多logn次就可以求出来了

然后观察，区间越大，gcd的范围是越来越小，或者不变的

然后我们可以来模拟一下，算一下每个数的贡献

对于 

16 4 7 21 3

从左到右就是

开个d数组 ，记录1到i的gcd

16 的贡献就是 16

d 1、2、3、4、5

  16 

然后4发现4和4的gcd是4,4和16的gcd是4，所以更新1位置的16

d 1、2、3、4、5

   4    4

4的贡献就是 4 + 4

再看 7，发现7 和 4的gcd是1，然后再去更新那些gcd不等于1的位置

d 1、2、3、4、5

   1    1   7

21的时候也是一样，21 和 7的gcd是7,然后再去更新发现7 和 3的gcd就变成1了以前是1不用修改

d 1 2 3 4 5 

   1 1 7 21

所以21的贡献就是 21 + 7 + 1 + 1

最后 3 ，3和21 gcd是 3，所以更新原来的，然后再去更新以前的7 

d 1 2 3 4 5 

   1 1 1 3 3

3的贡献就是 1 + 1 + 3 + 3 + 1

对于需要更新的位置直接更新就可以，然后不更新的位置用前缀和存一下，把d更新后，再更新一遍需要更新的前缀和，因为每次需要改变的gcd不超过log，所以每次更新最多也不会超过log

具体实现代码最好自己思考一下，实现一下：

ll c,n,k,m;
ll a[maxn],s[maxn],d[maxn];
int main() {
//    ios::sync_with_stdio(false);
    while(cin >> n){
        ll ans = 0;
        for(int i = 1;i <= n;i++) a[i] = read();
        for(int i = 1;i <= n;i++) d[i] = a[i];
        s[1] = a[1],d[1] = a[1];ans = a[1];
//        cout << ans << endl;
        for(int i = 2;i <= n;i++){
            ll Min = a[i],r = i;
            for(int j = i - 1;j >= 1;j--){
                    r = j;
                if(d[j] == Min)    break;
                else{
                    ll gcd = __gcd(Min,a[j]);
                    d[j] = gcd;
                    Min = gcd;
                }
            }
            for(int j = r - 1;j <= i;j++) s[j] = s[j - 1] + d[j];
            ans += s[i];
            ans %= mod;
        }
         cout << ans << endl;
    }
    cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}