首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;stdio.h&gt; int a[100000]; int main() {     int i, j, n, cnt;     scanf("%d", &amp;n);     cnt = n;   // 先假设所有的数都符合要求     for(i=0; i&lt;n; i++) { //输入 n 个元素         scanf("%d", &amp;a[i]);     }     for(int i=0; i&lt;n; i++) {         for(int j=0; j&lt;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 &lt;iostream&gt; using namespace std; int a[100000]; int main() {     int n, c;     cin &gt;&gt; n;     c = n;   // 先假设所有的数都符合要求     for(int i=0; i&lt;n; i++) {         cin &gt;&gt; a[i];     }     for(int i=0; i&lt;n; i++) {         for(int j=0; j&lt;n; j++) {             if(i==j)                 continue;             if(a[i] % a[j] == 0) {                 c--;  // 能整除则 个数减 1                 break;             }         }     }     cout &lt;&lt; c &lt;&lt; endl;     return 0; }</pre><p></p>
这道题暂未补解析。