约数个数

原题链接：870. 约数个数 - AcWing题库

解题思路

通过算术基本定理——任何一个大于1的自然数可以分解成一些质数的乘积。且表示方式唯一

一个数的因数个数 = 这个数的所有质因子的组合的数量 = 各个质因子的指数+1相乘（+1是因为不选这个质因子也是一个可能）

源代码

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    unordered_map<int,int> hash;
    int n;
    cin >> n;
    for(int j = 0;j < n;j ++)
    {
        int a;
        scanf("%d",&a);
        int b = a;
        for(int i = 2;i <= a / i;i ++)
        {
            int s = 0;
            while(b % i == 0)
            {
                hash[i] ++;
                b /= i;
            }
        }
        if(b > 1)
        {
            hash[b]++;
        }
    }
    long long re = 1;
    for(auto i : hash)
    {
        //if(i.first == 1)continue;
        re = (re * (i.second + 1)) % mod;
    }
    cout << re;
    return 0;
}