资讯详情

题目描述：
采用类似筛法的思想
范围给到1e6，可以枚举每个d，如果已经在数组中出现，直接continue，想要构造出d，至少要有两个d的倍数gcd=d，因为gcd具有非递增性，所有d的倍数的gcd一定不小于d，因为都是d的倍数，并且所有数gcd同时也是小于等于任意两个数gcd，所以d所有倍数gcd=d可以等价于可构造出d添加到数组中

include <bits/stdc++.h>

using namespace std;

define int long long

const int N=1000010;
const int mod= 1000000007;
//int a[N];
void solve()
{
int n,i,j,m=0;
cin >> n;
vector has(N+1,0);
for(i=0;i<n;i++)
{
int x;
cin >> x;
has[x]=1;
m=max(m,x);
}
int cnt=0;
for(i=1;i<=m;i++)
{
if(has[i]) continue;
int g=0;
for(j=1;j<=m/i;j++)
{
if(has[ji])
g=__gcd(g,ji);
}
if(g==i)
{
cnt++;
has[i]=1;
}
}
cout << cnt <<endl;
return ;
}
signed main ()
{
//int t;
// cin >> t;
//while(t--)
solve();
return 0;
}