A22930. 无法整除的数
填空题
较难
知识点
题目描述
无法整除的数
题目描述
给定一个长度为 N 的数列 A。
请计算满足以下条件的下标 i（1 ≤ i ≤ N）的数量：
对于任意 j（1 ≤ j ≤ N 且 i ≠ j），元素 Aᵢ 不能被 Aⱼ 整除。
输入格式
第一行，一个整数 N；
第二行，N 个整数表示 A₁,A₂,…,AN。
输出格式
输出一个整数，表示满足条件的下标数量。
输入样例#1
5
2 3 9 11 19输出样例#1
4输入样例#2
10
11 18 45 28 8 19 89 86 2 4输出样例#2
5参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,a[N];
bool cnt[N];
signed main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(!cnt[a[i]])
{
if(a[i] != a[i + 1]) ans++;
for(int j = a[i]; j <= 1e6; j += a[i]) cnt[j] = true;
}
}
printf("%d",ans);
}
上一题
下一题