Solution -「营业」「ABC 170D」Not Divisible

Description

Link.

给出一个长度为 (n) 的序列 (a)，求 (sum_{i=1}^{n}[forall jin[1,i)cup(i,n],a_{j} mid 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
",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
",ans);
	return 0;
}