[题解] AT2286 [ARC067A] Factors of Factorial

· · 题解

题目大意

求 n! （即 n 的阶乘）的约数个数。

分析

求约数个数，考虑用约数个数定理：

若一个正整数 n>1，且可分解为一系列质因数的积：

n=\prod_{i=1}^kp_i^{a_i}

则 n 的约数个数 f(n) 为：

f(n)=\prod_{i=1}^k(a_i+1)

接下来思考如何用该定理实现。

由于观察到数据并不大，n \le 1000，我们可以考虑从 1 到 n，每乘到一个数时，都分解一次质因数，用一个 map 数组统计可分解的质因数个数。中间的每个数可以分解的质因数指数都加 1，到最后就统计出了 n! 的质因数分解形式。时间复杂度 \mathcal{O}(n^2)。

思路如此，那么接下来介绍一下本题需要用到的 map 相关操作：

1、map <int, int> mp
（定义一个 map 类型的容器）
2、map <int, int> :: iterator p
（定义一个 map 类型的指针变量 p）
其中对于 mp[a]=b,p->first 表示 a,p->second 表示 b。
3、for (p=mp.begin(); p!=mp.end(); p++)
（遍历 map 数组）

那么 map 容器有何好处呢？

map 表示映射，即不需要像一般数组一样占用太多的内存，并且可以支持负数下标。

map 还有其他较为常用的函数，可以参考oi-wiki。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mo = 1e9 + 7;
int n, s=1;
map <int, int> mp;
map <int, int> :: iterator p;
void work(int x){
    for (int i=2; i<=x; i++) while (x % i == 0) x /= i, mp[i] ++;
}
signed main(){
    scanf ("%lld", &n);
    for (int i=1; i<=n; i++) work(i);
    for (p=mp.begin(); p!=mp.end(); p++) s = s *  (p->second + 1) % mo;
    printf ("%lld\n", s);
    return 0;
}