Code: Select all
#include <iostream>
using namespace std;
int n;
const int maxn = 1000000;
//const int maxn=20;
int a[maxn];
int b[maxn];
int c[maxn];
void copyarr(int *src, int *dest)
{
for (int i = 0; i <= n; i ++)
{
dest[i] = src[i];
}
}
void addarr(int *src1, int *src2, int *dest)
{
for (int i = 0; i <= n; i ++)
{
dest[i] = src1[i] + src2[i];
}
}
int count(int *src)
{
int cnt = 1;
for (int i = 2; i <= n; i ++)
{
cnt *= (src[i] + 1);
cnt %= 1000000007;
}
return (cnt);
}
void fac(int *src, int j)
{
int p = 1, st = 1;
while (j > 1)
{
p += st;
while (j % p == 0)
{
src[p] ++;
j /= p;
}
if (p == 2)
{
p = 1;
st = 2;
}
}
}
int main()
{
int i, cnt;
cin >> n;
for (i = 0; i <= n; i ++)
{
a[i] = 0; b[i] = 0; c[i] = 0;
}
for (i = 2; i <= n; i ++)
{
addarr(a, b, c);
fac(c, i);
copyarr(b, a);
copyarr(c, b);
}
cout << count(c) << endl;
return (0);
}
There must be some math optimization reduction based on number theory.