---
title: "约数个数"
created: 2025-11-28
tags:
  - 算法
---

# 约数个数

## 题目 [约数个数](https://www.acwing.com/problem/content/872/)

![[image-9c14b5c1.png]]

## 思路分析

首先还是想暴力 把最后的数算出来 然后用试除法求得约数在set里 最后取出set的size就是答案

```cpp
#include<bits/stdc++.h>

using namespace std;

const int mod=1e9+7;

set<int> get_divisors(int n){

    set<int> res;

    for(int i=1;i<=n/i;i++){

        if(n%i==0){

            res.insert(i);

            res.insert(n/i);

        }

    }

    return res;

}

int main()

{

    int n;cin>>n;

    long long sum=1;

    while(n--){

        int a;cin>>a;

        sum*=a; cout<<"sum "<<sum<<endl;

    }

    auto res=get_divisors(sum);

        cout<<res.size()%mod;

    return 0;

}
```

这里用的是相乘 先抛开时间不说 都找不到一个合适的数据类型存放最终的数

![[image-209ce011.png]]

第三组数据就爆了 还是long long

学习一个新思路

类似于排列问题

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

例如：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)

![[image-a21d2047.png]]

那么问题转变成 把每个数 分解质因数出来 把每个质因数（基数）出现的次数（指数）累加起来

最后再使用每个基数的指数统一进行计算

显然可以用哈希表

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int mod=1e9+7;

unordered_map<int,int> Weight;

int T;

int main()

{

    cin>>T;

    while(T--){

        int n;cin>>n;

        for(int i=2;i<=n/i;i++){

            while(n%i==0){

                Weight[i]++;

                n/=i;

            }

        }

        if(n>1)

            Weight[n]++;

    }

    long long res=1;

    for(auto x:Weight){

        res=res*(x.second+1)%mod;

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[等差数列|等差数列]] 🏠 [[00-刷题理模型]] ➡️ [[约数之和|约数之和]]