Description
Link.
给出一个长度为 \(n\) 的序列 \(a\)，求 \(\sum_{i=1}^{n}[\forall j\in[1,i)\cup(i,n],a_{j}\nmid a_{i}]\)。
Solution
首先特判序列中有 \(1\) 的情况。
然后调和级数把每个数的倍数开桶记录。
最后扫一遍序列，看该元素在桶里面出现的次数不超过一就有贡献。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=0,f=0; char ch=getchar();
while(ch<‘0‘||ch>‘9‘) f|=(ch==‘-‘),ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch&15),ch=getchar();
return f?-x:x;
}
const int N=200100,M=1000000;
int a[N],bc[M];
signed main()
{
int n=read();
for(int i=1;i<=n;++i) a[i]=read();
int cnt=0,ans=0;
for(int i=1;i<=n;++i) (a[i]==1)&&(++cnt);
if(cnt) return printf("%d\n",cnt>1?0:1),0;
for(int i=1;i<=n;++i) for(int j=a[i];j<=M;j+=a[i]) ++bc[j];
for(int i=1;i<=n;++i) (bc[a[i]]<=1)&&(++ans);
printf("%d\n",ans);
return 0;
}