约数
TH讠NK
·
·
个人记录
约数
若正整数 N 被唯一分解成 N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m} ，则 N 的正约数集合可写作： {\{ p_1^{b_1}p_2^{b_2}\cdots p_m^{b_m} \}} , 其中 0 \le b_i \le c_i
$$(c_1+1)*(c_2+1)* \cdots *(c_m+1)=\prod\limits_{i=1}^m (c_i+1)$$
$N$ 的所有正约数之和为：
$$(1+p_1+p_1^2+ \cdots +p_1^{c_1})* \cdots *(1+p_m+p_m^2+ \cdots +p_m^{c_m})=\prod\limits_{i=1}^m (\sum\limits_{j=0}^{c_i} (p_i)^j)$$
求 $N$ 的正整数集合可以用**试除法**实现
```cpp
for(int i=1;i*i<=n;i++)
if(n%i==0){
c[++cnt]=i;
if(i*i!=n) c[++cnt]=n/i;
}
for(int i=1;i<=cnt;i++) cout<<c[i]<<endl;
```
**推论：** 一个整数 $N$ 的约数不会超过 $2 \sqrt{N}