OO’s Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1751 Accepted Submission(s): 632

Problem Description

OO has got a array A of size n ,defined a function f(l,r) represent the number of i (l<=i<=r) , that there's no j(l<=j<=r,j<>i) satisfy a

_i mod a

_j=0,now OO want to know

\sum i = 1 n \sum j = i n f (i, j) m o d （ 109 + 7 ） .

Input

There are multiple test cases. Please process till EOF.

In each test case:

First line: an integer n(n<=10^5) indicating the size of array

Second line:contain n numbers a

_i(0<a

_i<=10000)

Output

For each tests: ouput a line contain a number ans.

Sample Input

       5 1 2 3 4 5 

Sample Output

23

Author

FZUACM

Source

Recommend

We have carefully selected several similar problems for you:

题意非常easy ：求随意区间内满足条件的ai有多少个

假设依照题意程序应该这样写：

四层循环 - - （不超时吃键盘）

尽管最后优化到 n^2/2也超时数据太大了

#include
      
       int main(){    int n,i,j,k,kk,a[100050];    while(scanf("%d",&n)!=EOF)    {        for(i=1; i<=n; i++)            scanf("%d",&a[i]);        long long suma=0;        for(i=1; i<=n; i++)        {            for(j=i; j<=n; j++)            {                for(k=i; k<=j; k++)//相当于i                {                    int flag=0;                    for(kk=i; kk <= j ; kk++)//相当于j                    {                        if(a[k]%a[kk] == 0 && k!=kk)                        {                            flag=1;                            break;                        }                    }                    if(flag!=1)                    {                        suma++;                        suma%=100000007;                    }                }                printf("%d %d=%d %d=%d\n",i,j,a[i],a[j],suma);            }        }        printf("%I64d\n",suma);    }}

脑洞大开：换个思路是不是题意求的是找那些区间能满足第ai个值存在呢？

也就是说看ai能提供几个答案

定义两个数组 l r 表示i数的左側和右側

最接近他的值且值是a[i]因子的数字的位置

那么第i个数字能提供的答案就是(r[i]-i) * (l[i]-i)

事实上这样的方法有漏洞假设我给你 10w个1 程序就跪了 ╮(╯▽╰)╭ 没有这数据所以放心大胆的做吧

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int M = 10e5 + 5;const long mod = 1e9+7;int vis[M],a[M],l[M],r[M];int main(){    int n;    while(~scanf("%d",&n))    {        memset(l,0,sizeof(l));        memset(r,0,sizeof(r));        memset(vis,0,sizeof(vis));        for(int i = 1;i <= n; ++i)        {            scanf("%d",&a[i]);            r[i] = n+1;            for(int j = a[i];j <= 10000; j+=a[i]) //找到离他近期的因子            {                if(vis[j])                {                    r[vis[j]] = i;                    vis[j] = 0;                }            }            vis[a[i]] = i;        }        memset(vis,0,sizeof(vis));        for(int i = n;i >= 1; --i)        {            for(int j = a[i];j <= 10000; j+=a[i])            {                if(vis[j])                {                    l[vis[j]] = i;                    vis[j] = 0;                }            }            vis[a[i]] = i;        }        long long ans = 0;        for(int i = 1;i <= n; ++i)        {        ans = ((ans + (long long)(r[i]-i)*(long long)(i-l[i])%mod)%mod);        }        printf("%I64d\n",ans);    }}