OO’s SequenceTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2643Accepted 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 ai mod 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
Source
2015 Multi-University Training Contest 1
Recommend
#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<functional>#include<iostream>#include<cmath>#include<cctype>#include<ctime>#include<vector>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<n;i++)#define ForD(i,n) for(int i=n;i;i–)#define RepD(i,n) for(int i=n;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<<al[i]<<' ';cout<<endl;// For(i,n) cout<<ar[i]<<' ';cout<<endl;//For(i,n)upd(ans,mul(i-al[i],ar[i]-i));<span style="white-space:pre"></span>cout<<ans<<endl;}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
失败是成功的亲娘，没有失败哪来的成功呢?诺贝尔如果不经历千万次的失败，
