约数个数公式

题目是求有 100 个约数的数字的最小值。有两种方法去做，一种直接暴力求每个数的约数个数，直到找到第一个约数为 100 的数。第二种用到了约数定理，首先用质因数分解的方法求出每个质因数的指数：

$$n = a_{1}^{p1}*a_{2}^{p2}*...*a_{n}^{pn}$$

那么 n 的约数个数可以用以下公式求得：

$$(p1+1)*(p2+1)*...*(pn+1)$$

很简单的乘法原理的思想，对于质因数 $ a_1 $ 可以取 0,1,2…n 一共 n+1 个，其他同理。
如何证明这样不会取得相同的因数呢？
假设两个因数

$$b_1 = a_1 * a_1 * a_2 * a_2 * a_3 \\ b_2 = a_1 * a_2 * a_3 * a_4$$

如果 $ b_1 = b_2 $ 那么有 $ a_1 * a _2 = a_4 $，显然与$a_4$是一个质数矛盾，所以不存在重复的情况。
代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int solve(int n)
{
    int factor = 2, cnt = 0;
    vector<int> a;
    while (n != 1)
    {
        if (n % factor != 0)
        {
            factor++;
            a.push_back(cnt);
            cnt = 0;
        }
        else
        {
            n = n / factor;
            cnt++;
        }
    }
    a.push_back(cnt);

    int sum = 1;
    for (int i = 0; i < a.size(); i++)
    {
        sum *= (a[i] + 1);
    }
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    freopen("data.in", "r", stdin);
    int n = 1;
    while (1)
    {
        int ret = solve(n);
        // cout << ret << endl;5
        if (ret == 100)
        {
            cout << n << endl;
            break;
        }
        n++;
    }
    return 0;
}