View Code of Problem 3571

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
const int mod=1000000007;
set<ll> f[10005];
ll L[100005],R[100005],a[100005],vis[100005];
bool primer[10005];
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(ll i=1;i<=n;i++)
        {
            a[i]=read();
            L[i]=1;
            R[i]=n;
        }
        memset(vis,0,sizeof(vis));  //vis记录该数的倍数之前是否已经算过了,顺便记录位置
        for(ll i=1;i<=n;i++)
        {
            for(ll j=a[i];j<=10000;j+=a[i])
            {
                if(vis[j]&&R[vis[j]]==n)    //如果vis>0，说明a[i]的倍数j在之前出现过，说明a[i]是vis那位置的因子
                    R[vis[j]]=i-1;
            }
            vis[a[i]]=i;
        }
        memset(vis,0,sizeof(vis));
        for(int i=n;i>0;i--)
        {
            for(ll j=a[i];j<=10000;j+=a[i])
            {
                if(vis[j]&&L[vis[j]]==1)
                    L[vis[j]]=i+1;
            }
            vis[a[i]]=i;
        }
        ll ans=0;
        for(ll i=1;i<=n;i++)
        {
            ans=(ans%mod+(i-L[i]+1)*(R[i]-i+1)%mod)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}