OO’s Sequence

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

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

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i
                  
                   =0;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (1000000007)#define MAXN (1000000+10)#define MAXn (1000000+10)typedef long long ll;ll mul(ll a,ll b){return (a*b)%F;}ll add(ll a,ll b){return (a+b)%F;}ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}void upd(ll &a,ll b){a=(a%F+b%F)%F;}int a[MAXn],n;ll l[MAXN],r[MAXN];ll al[MAXN],ar[MAXN];int main(){// freopen("A.in","r",stdin);// freopen(".out","w",stdout); while(scanf("%d",&n)==1) { ll ans=0; For(i,n) scanf("%d",&a[i]); MEM(l) MEMI(r) For(i,n) { al[i]=0; int p=a[i]; for(int j=1;(ll)j*j<=(ll)p;j++) { if (p%j==0) al[i]=max(al[i],max(l[j],l[p/j])); } l[a[i]]=i; } ForD(i,n) { ar[i]=n+1; int p=a[i]; for(int j=1;(ll)j*j<=(ll)p;j++) { if (p%j==0) ar[i]=min(ar[i],min(r[j],r[p/j])); } r[a[i]]=i; } // For(i,n) cout<
                   
                    <<' ';cout<