[AcWing]870. 约数个数（C++实现）求约数个数模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

思路：

什么是约数？
约数，又称因数。整数a除以整数b(b≠0)，除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

约数个数怎么求？
一个数N分解质因数为如下形式：

因此，约数的个数的公式为：

这个公式是怎么得到的呢？

代码实现的思路：
1、在每次输入一个数时，分解其质因数，将其出现的次数保存起来；
2、遍历保存质因数的表，将每个质因数出现的次数+1再相乘即可（即约数个数公式）。

---------------------------------------------------解法---------------------------------------------------

#include
#include
#include
#include

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9+7;

int main(){
    int n;
    cin >> n;
    unordered_map primes;
    // 每次将输入的数分解质因数，质因数放在primes中
    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ ) // 分解质因数
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ; // 保存最后一个质因数
    }
        LL res = 1;
        for(auto p : primes) res = res*(p.second+1) % mod;
        cout << res << endl;
        return 0;
}

• [AcWing]867. 分解质因数（C++实现）试除法模板题

约数个数的模板题，熟记并背下来。