2019年华南理工大学程序设计竞赛（春季赛）-H-Parco_Love_GCD

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

题意：给定n个数（<=1e9）的序列，其中n<=5e5，求该序列所有子序列的对应的gcd对1e9+7取模后的值。

思路：比赛的看错题了，以为是要求n个数任意两个数的gcd的和，怪样例QAQ。。不过就算我没看错题我可能也做不出来。先把n个数的公共gcd求出来，记为com。然后对每个子序列的起点往后求gcd，记为nwa，令 ans=(ans+nw)%Mod; 如果nw=com，就不用再循环了，ans=(ans+(n-j)*com)%Mod。这样做用两层循环也可以过，有点惊讶，n大小可是5e5，但想想之后觉得也没问题，他们的公共gcd--com很可能为1，只要求到1的时候break，复杂度应该会降很多。加上这道题的时间限制为3s，这样做就没问题了。另外我写的时候写太快，不小心把数组开成了5e5大小了，下标从1开始，然后T了，想不懂的是为什么会T，不应该是RE吗。。总之把数组开大一点很重要。

AC代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

using namespace std;

typedef long long LL;

inline LL readLL(){

    LL x=;int f=;char c=;

    while(!isdigit(c)){f|=c=='-';c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

LL gcd(LL a,LL b){

    return b?gcd(b,a%b):a;

}

const int Mod=;

LL n,ans,a[],com;

int main(){

    n=readLL();

    com=a[]=readLL();

    for(int i=;i<=n;++i){

        a[i]=readLL();

        com=gcd(com,a[i]);

    }

    for(int i=;i<=n;++i){

        LL nw=a[i];

        for(int j=i;j<=n;++j){

            nw=gcd(nw,a[j]);

            ans=(ans+nw)%Mod;

            if(nw==com){

                ans=(ans+(n-j)*com)%Mod;

                break;

            }

        }

    }

    printf("%lld\n",ans);

    return ;

}

2019年华南理工大学程序设计竞赛（春季赛）-H-Parco_Love_GCD的相关教程结束。