給你n個數,讓你找到所有區間內不能整除其它數的數的個數之和
#include
#include
#include
using namespace std;
const int mod = 1e9+7;
#define ll long long
#define N 111111
ll l[N],r[N];//存儲左邊因子。右邊因子的位置
int n,m;
int pre[N],last[N];
int a[N];
int main(){
while(scanf(%d,&n)==1){
for(int i=1;i<=n;i++) {
scanf(%d,&a[i]);
l[i]=1;
r[i]=n;//初始化最左邊的因子和最右邊的因子都是本身
}
memset(pre,0,sizeof(pre));
memset(last,0,sizeof(last));
for(int i=1;i<=n;i++){
for(int j=a[i];j<=10000;j+=a[i])
if(pre[j]!=0&&r[pre[j]]==n)//如果已經出現並且在右邊最近的因子還沒有找到
r[pre[j]]=i-1;
pre[a[i]]=i;
}
for(int i=n;i>0;i--){
for(int j=a[i];j<=10000;j+=a[i])
if(last[j]!=0&&l[last[j]]==1)//如果已經出現並且在左邊最近的因子還沒有找到
l[last[j]]=i+1;
last[a[i]]=i;
}
/*
for(int i=1;i<=n;i++){
printf(%d %d %d
,i,l[i],r[i]);
}
*/
ll ans = 0;
for(int i=1;i<=n;i++){
ans = (ans%mod+(ll)(i-l[i]+1)*(r[i]-i+1)%mod)%mod;
}
printf(%I64d
,ans);
}