链接‘

开始有所没读明白题orz 一上午终于看懂了 已知n个数 相对顺序固定 如果存在子区间 使得任意a[i]不能整除区间里的其他数 区间长度之和是多少？

借用网友的思路：每个a[i]所在范围有左右顶点分别是l[i]和r[i] 则题目转化为求(i-l[i]+1)*(r[i] - i + 1)

以r[i]为例：假设最开始每枚举一个数a[i]的区间的右顶点是n即总区间最右，在第二重循环中枚举此数的倍数值若左边出现了这个倍数那么r[i]找到了

同理

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 100010 ;
const int mod = 1e9+7 ;
int a[maxn];
typedef __int64 ll ;
ll last[maxn] ;
ll pre[maxn] ;
ll l[maxn] ;
ll r[maxn] ;
int  main()
{
   // freopen("cin.txt" ,"r" ,stdin) ;
    int n ;
    while(~scanf("%d" ,&n))
    {
        memset(last , 0 ,sizeof(last)) ;
        memset(pre , 0 ,sizeof(pre)) ;
        for(ll i=1;i<=n;i++)scanf("%d" ,&a[i]) ;
        for(ll i =1;i <= n;i++)
        {
            r[i] = n ;
            for(ll j = a[i] ;j < maxn/10;j+=a[i])
                if(pre[j] != 0 && r[pre[j]] == n)
                    r[pre[j]] = i - 1;
            pre[a[i]] = i;
        }
        for(ll i = n ;i >= 1;i--)
        {
            l[i] = 1;
            for(ll j = a[i];j < maxn/10;j+=a[i])
                if(last[j] != 0 && l[last[j]] == 1)
                    l[last[j]] = i + 1;
            last[a[i]] = i ;
        }
        ll ans = 0 ;
        for(ll i = 1;i <= n;i++)
        {
            //printf("l[i]=%I64d   r[i]=%I64d   pre[i]=%I64d   last[i]=%I64d\n",l[i],r[i],pre[i],last[i]);
            ans = (ans + (((i-l[i]+1)%mod)*((r[i] - i + 1)%mod))%mod)%mod ;
        }
        printf("%I64d\n" ,ans) ;
    }
    return 0 ;
}