AcWing 870. 约数个数---海绵宝宝来喽

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 870. 约数个数---海绵宝宝来喽原题链接简单

作者：

Hasity , 2022-11-13 13:47:47 , 所有人可见 , 阅读 5773

278

28

$\color{green}{<–画图不易，点下这里赞一下吧}$

思路

一个数的约数是由这个数的几个质因子相乘得到的。

例如：12 的质因子有 2，3。12的约数有：1，2，3，4，6，12。

约数1 是由 0 个 2， 0 个3相乘得到的。
约数2 是由 1 个 2， 0 个3相乘得到的。
约数3 是由 0 个 2， 1 个3相乘得到的。
约数4 是由 2 个 2， 0 个3相乘得到的。
约数6 是由 1 个 2， 1 个3相乘得到的。
约数12 是由 2 个 2， 1 个3相乘得到的。

12 可以分解为：2^2*3^1。所以2可以取 0 ~ 2个，3种取法。3可以取 0~1 个，2种取法。12的约数一共：2 * 3 = 6个。

也就是：把一个数N 写成：N = (p1^x1^)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)

理论点的证明

写了也没人看。

代码

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9+7 ;
int main()
{
    int T; 
    cin >> T;
    unordered_map<int, int> h;
    while(T--)
    {
        int n; cin >> n;
        //依次求出指数
        for(int i = 2; i <= n / i; i++)
        {
            while(n % i == 0)
            {
                //指数+1
                h[i] ++;
                n = n / i;
            }
        }
        //如果有剩余，也是一个质因子
        if(n > 1) h[n]++;
    }

    long long  res = 1;
    for(auto iter = h.begin(); iter != h.end(); iter++)
    {
        //res = (x1+1)(x2+1)(x3+1)…(xk+1)
        res = res * (iter->second + 1) % mod ;
    }
    cout << res;
}