3377.约数的个数
| 3377. 约数的个数 - AcWing题库 |
|---|
| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：3529 |
| 总尝试数：6834 |
| 来源： 清华大学考研机试题 |
| 算法标签 数学知识约数试除法因式分解 |
题目内容
输入 n 个整数，依次输出每个数的约数的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 ai。
输出格式
共 n 行，按顺序每行输出一个给定整数的约数的个数。
数据范围
1≤n≤1000,
1≤ai≤10^9
输入样例：
5
1 3 4 6 12
输出样例：
1
2
3
4
6
题目解析
分别计算每个整数的约数的个数
用试除法的话，时间复杂度是
1
0
9
\sqrt{ 10^9 }
109，3万多
有1000个数据
3000万的计算量
优化
求约数个数是有一个公式的
把a的因式分解求出来
a
=
P
1
a
1
P
2
a
2
…
P
k
a
k
a = P_{1}^{a_{1}}P_{2}^{a_{2}}\dots P_{k}^{a_{k}}
a=P1a1P2a2…Pkak
a的所有约数d
包含的质因子只能从这k个质因子中选
它不可能包括这k个质因子以外的质因子，如果包含的话就不能整除a了
d的不同就取决于每个质因子的次数
设
d
=
P
1
b
1
P
2
b
2
…
P
k
b
k
d = P_{1}^{b_{1}}P_{2}^{b_{2}}\dots P_{k}^{b_{k}}
d=P1b1P2b2…Pkbk
每个质因子是完全独立的
只要保证
0
≤
b
i
≤
a
i
0 \le b_{i} \le a_{i}
0≤bi≤ai
超过的话就不能整除了
只要不超过，就一定是可以整除的，是一个约数
满足这个条件下，d总共有多少种选择
每一个b都是独立的
如果想求选法个数的话，可以用乘法原理
先看一下
b
1
b_{1}
b1的选法的数量，
b
1
b_{1}
b1可以从0选到
a
1
a_{1}
a1，所以
b
1
b_{1}
b1的选法就是
a
1
+
1
a_{1}+1
a1+1种选择
b
2
b_{2}
b2就是
a
2
+
1
a_{2}+1
a2+1
以此类推，
b
k
b_{k}
bk的选法数量就是
a
k
+
1
a_{k}+1
ak+1
因此约数个数就等于
每个质因子次数+1 相乘
可以用分解质因式的方式来求约数个数
代码
试除法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int calc(int x)
{
//res表示约数个数
int res = 0;
for (int i = 1; i <= x / i; i ++)
if (x % i == 0)
{
res ++;
if (i != x / i) res ++;
}
return res;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
//输出x的约数的个数
cout << calc(x) << endl;
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int calc(int x)
{
//res表示约数个数
//要连乘，连乘的零元就是1
int res = 1;
//把x分解质因式
for (int i = 2; i <= x / i; i ++)
//如果i是x的一个因数的话，i此时一定是质因子
if (x % i == 0)
{
//用s表示i的次数
int s = 0;
//把x当中的i除干净
while (x % i == 0) x /= i, s ++;
res *= (s + 1);
}
//如果x大于1，表示存在大于根号x的质因子，次数是1
if (x > 1)
res *= 2;
return res;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
//输出x的约数的个数
cout << calc(x) << endl;
}
return 0;
}