题目描述
输入 $n$ 个整数,依次输出每个数的约数的个数。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个整数 $a_i$。
输出格式
共 $n$ 行,按顺序每行输出一个给定整数的约数的个数。
数据范围
$1 \le n \le 1000$,
$1 \le a_i \le 10^9$
输入样例:
5
1 3 4 6 12
输出样例:
1
2
3
4
6
算法1
(暴力枚举) $O(n^2)$
通过试除法确定个数
当 $x$ 能被 $i$ 整除时,答案加 $1$,如果 $x ÷ i$ 不为 $i$,同样是一种方案。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int main(){
scanf("%d",&n);
while(n -- ){
int x;
scanf("%d",&x);
int res = 0;
for(int i = 1;i <= x / i;i ++){
if(x % i == 0){
res ++;
if(x / i != i) res ++;
}
}
printf("%d\n",res);
}
return 0;
}