C++14(g++5.4) 解法, 执行用时: 326ms, 内存消耗: 2424K, 提交时间: 2019-04-13 14:20:41

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,mod=1e9+7;
int a[500005];
int main(){
	int n,g;
	scanf("%d%d",&n,&a[1]);
	g=a[1];
	for(int i=2;i<=n;i++){
		scanf("%d",&a[i]);
		if(g!=1)g=__gcd(g,a[i]);
	}
	for(int i=1;i<n;i++){
		int t=a[i],j;
		ans=(ans+a[i])%mod;
		for(j=i+1;j<=n;j++){
			t=__gcd(t,a[j]);
			ans+=t;
			if(t==g)break;
		}
		if(j<n)ans+=1ll*g*(n-j);
	}
	printf("%lld\n",(ans+a[n])%mod);
    return 0;
}

C 解法, 执行用时: 268ms, 内存消耗: 12056K, 提交时间: 2022-05-18 21:30:34

#include<stdio.h>
#define ll long long
#define N 1000010
#define P 1000000007;
ll n,i,j,ans,a[N],l[N],v[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
  scanf("%lld",&n);
  for(i=1;i<=n;i++)scanf("%lld",&a[i]);
  for(i=1;i<=n;i++)
  for(v[i]=a[i],j=l[i]=i;j;j=l[j]-1)
  {
    v[j]=gcd(v[j],a[i]);
    while(l[j]>1&&gcd(a[i],v[l[j]-1])==gcd(a[i],v[j]))l[j]=l[l[j]-1];
    ans=(v[j]*(j-l[j]+1)+ans)%P;
  }
  printf("%lld",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 317ms, 内存消耗: 9556K, 提交时间: 2019-04-18 18:41:39

#include<bits/stdc++.h>
const int N=500010,P=1000000007;
int n,i,j,ans,a[N],l[N],v[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]);
  for(i=1;i<=n;i++)for(v[i]=a[i],j=l[i]=i;j;j=l[j]-1){
    v[j]=gcd(v[j],a[i]);
    while(l[j]>1&&gcd(a[i],v[l[j]-1])==gcd(a[i],v[j]))l[j]=l[l[j]-1];
    ans=(1LL*v[j]*(j-l[j]+1)+ans)%P;
  }
  printf("%d",ans);
}