简答题
偏难
#13133
无法整除的数 给定一个长度为 N 的数列 A。请计算满足以下条件的下标 i(1≤i≤N)的数量: 对于任意 j(1≤j≤N且 i≠j),元素 A i 不能被 A…
无法整除的数
给定一个长度为 N 的数列 A。请计算满足以下条件的下标 i(1≤i≤N)的数量:
对于任意 j(1≤j≤N且 i≠j),元素 Ai 不能被 Aj 整除。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,一个整数 N;
第二行,N 个整数表示 A1、A2、……、AN。
输出格式
输出一个整数,表示满足条件的下标数量。
输入样例#1
5 2 3 9 11 19
输出样例#1
4
输入样例#2
10 11 18 45 28 8 19 89 86 2 4
输出样例#2
5
数据范围:
所有输入均为整数;1≤N≤2×105;1≤Ai≤106。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C语言
#include <stdio.h>
int a[100000];
int main() {
int i, j, n, cnt;
scanf("%d", &n);
cnt = n; // 先假设所有的数都符合要求
for(i=0; i<n; i++) { //输入 n 个元素
scanf("%d", &a[i]);
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j)
continue;
if(a[i] % a[j] == 0) {
cnt--; // 能整除则 个数减 1
break;
}
}
}
printf("%d", cnt);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//C++
#include <iostream>
using namespace std;
int a[100000];
int main() {
int n, c;
cin >> n;
c = n; // 先假设所有的数都符合要求
for(int i=0; i<n; i++) {
cin >> a[i];
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j)
continue;
if(a[i] % a[j] == 0) {
c--; // 能整除则 个数减 1
break;
}
}
}
cout << c << endl;
return 0;
}</pre><p></p>
这道题暂未补解析。