点击打开链接
OO’s SequenceTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1317Accepted Submission(s): 467
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 aimod aj=0,now OO want to know
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 arraySecond line:contain n numbers ai(0<ai<=10000)
Output
For each tests: ouput a line contain a number ans.
Sample Input
51 2 3 4 5
Sample Output
23
Author
FZUACM
f(l,r)表示l<=i<=r，，对任意l<=j<=r,j!=i,i%j!=0，i的个数
求所有f(l,r)之和
开两个数组l[i]和r[i]记录离a[i]最近的是a[i]因数或倍数的下标
由于a[i]小于10000
枚举是a[i]倍数的数就可以
代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define MAXN 111111#define MOD 1000000007using namespace std;int l[MAXN],r[MAXN],pre[MAXN];int a[MAXN];int main(){int n;while(scanf("%d",&n)!=EOF){memset(pre,0,sizeof(pre));for(int i=1;i<=n;i++){l[i]=1;r[i]=n;scanf("%d",&a[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;}memset(pre,0,sizeof(pre));for(int i=n;i>=1;i–){for(int j=a[i];j<=10000;j+=a[i])if(pre[j]!=0&&l[pre[j]]==1)l[pre[j]]=i+1;pre[a[i]]=i;}long long ans=0;for(int i=1;i<=n;i++)ans=(ans+(i-l[i]+1)*(r[i]-i+1))%MOD;printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生的大部份时间里，承诺同义词是束缚，奈何我们向往束缚。
