# 因素和

求一个自然数 n 的所有因数之和

# 暴力筛

复杂度 O (nlogn)
即准备一个长度为 n 的数组 f [n]，表示 n 的因数和，令 i 遍历 1~n ，若 i 是 j 的因数，则 f [j]+=i。
+++ 代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
ll f[N],s;
int n;
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j+=i)
        {
            f[j] += i;
        }
    }
}

+++

# 线性筛

参考资料戳此处
复杂度 O (n)
（需要了解欧拉筛）
由算术基本定理，任意自然数 n 可表示为
n = p1k1p2k2…pnknp_1^{k_1}p_2^{k_2}…p_n^{k_n}
则其因数和为
(1+p1p_1+p12p_1^2+…+p1k1p_1^{k_1})(1+p2p_2+p22p_2^2+…+p2k2p_2^{k_2})…(1+pnp_n+pn2p_n^2+…+pnknp_n^{k_n})
又可以写为
∑i=0n∑j=0kipij\sum_{i=0}^n\sum_{j=0}^{k_i}p_i^j

# 求三角形面积

# 海伦公式

S=p(p−a)(p−b)(p−c)S = \sqrt{p(p-a)(p-b)(p-c)}

其中

p=a+b+c2p = \frac{a+b+c}{2}

# 秦九韶公式

S=14[a2b2−(a2+b2−c22)2]S = \sqrt{\frac{1}{4}[a^2b^2-(\frac{a^2+b^2-c^2}{2})^2]}