AtCoder 2286 C - Factors of Factorial（因子数）

题目链接：http://arc067.contest.atcoder.jp/tasks/arc067_a?lang=en

C - Factors of Factorial

---

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

You are given an integer N. Find the number of the positive divisors of N!, modulo 109+7.

Constraints

1≤N≤103

---

Input

The input is given from Standard Input in the following format:

N

Output

Print the number of the positive divisors of N!, modulo 109+7.

---

Sample Input 1

Copy 3

Sample Output 1

Copy 4

There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.

---

Sample Input 2

Copy 6

Sample Output 2

Copy 30

---

Sample Input 3

Copy 1000

Sample Output 3

Copy 972926972

---

Submit

题意：求n!的因子数

解析：n = 2^x1 + 3^x2 + 5^x3 + 7^x4 + 11^x5............ 就是一个数素因子分解，n的因子就是 sum =  (x1+1) * (x2+1) * (x3+1)  * ...............

代码：

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<cmath> #define N 1009 using namespace std; const int INF = 0x3f3f3f3f; const long long mod = 1e9 + 7; int fun(int n) { int f[N]; memset(f, 0, sizeof(f)); long long ans = 1; for(int i = 2; i <= n; i++) { int k = i; for(int j = 2; j <= k; j++) { while(k % j == 0) { f[j]++; k /= j; } } if(k) f[k]++; } for(int i = 2; i <= n; i++) if(f[i]) ans = ans * (f[i] + 1) % mod; return ans % mod; } int main() { int n; scanf("%d", &n); cout << fun(n) << endl; return 0; }