Description 小明有一个数列。 a[0] = a[1] = 1。 a[i] = i * a[i - 1] * a[i - 2]（i≥2）。 小明想知道a[n]的因子个数。
Input 输入仅一个正整数n。
Output 输出a[n]的因子个数mod 1,000,000,007的值。
Sample Input 3
Sample Output 4
Hint 【数据范围】 对于30%的数据满足0≤n≤1,000。 对于100%的数据满足0≤n≤1,000,000。
分析：不难发现a[x]=x*(x-1)*(x-2)^2 *(x-3)^3 *(x-4)^5…… 因此它们的指数是一个斐波那契数列，然后就可以用算术基本定理的推论求约数个数了
代码
#include <cstdio> #define N 1000005 #define ll long long #define mo 1000000007 using namespace std; int n; ll f[N],a[N]; bool v[N]; int main() { scanf("%d", &n); f[1] = f[2] = 1; for (int i = 3; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % mo; for (int i = 2; i <= n; i++) { if (v[i]) continue; a[i] = f[n - i + 1]; for (int j = i * 2; j <= n; j+=i) { v[j] = true; int x = j; while (x % i == 0) { a[i] = (a[i] + f[n - j + 1]) % mo; x /= i; } } } ll ans = 1; for (int i = 1; i <= n; i++) ans = ans * (a[i] + 1) % mo; printf("%lld", ans); }