The main idea of the title
we define
f
(
x
)
=
x
1
×
(
x
?
1
)
2
×
(
x
?
2
)
3
×
?
×
2
x
?
1
×
1
x
f(x)=x^1\times (x-1)^2\times (x-2)^3\times \cdots\times 2^{x-1}\times 1^x
f(x)=x1×(x?1)2×(x?2)3×?×2x?1×1x. given
n
n
n, find
f
(
n
)
f(n)
Prime factorization form of f(n).
beg
f
(
n
)
f(n)
The prime factor decomposition form of f(n) is required to be arranged according to the size of the prime factors. When the exponent is
1
1
When 1, the exponent should be ignored. See the example for specific format requirements.
Sample output
5
Sample output
f(5)=2^8*3^3*5
Sample explanation
f
(
5
)
=
2
4
×
3
3
×
4
2
×
5
1
=
2
8
×
3
3
×
5
f(5)=2^4\times 3^3\times 4^2\times 5^1=2^8\times 3^3\times 5
f(5)=24×33×42×51=28×33×5
Data range
1
≤
n
≤
1
0
7
1\leq n\leq 10^7
1≤n≤107
Solution
First, we can use the Euler sieve to find
1
0
7
10^7
Prime numbers within 107
p
i
p_i
pi? and, the smallest prime factor of each number
l
t
i
lt_i
lti?.
we use
t
i
t_i
ti? represents the number of times each number is currently not included in the answer, using
c
i
c_i
ci? represents each prime number
i
i
i final number of times.
We enumerate from largest to smallest
i
i
i, for each
i
i
i, will
i
i
i is divided into
l
t
i
lt_i
lti?and
i
l
t
i
\dfrac{i}{lt_i}
lti?i?.
l
t
i
lt_i
lti? is a prime number, so we can
i
i
The number of times i contributes to
c
l
t
i
c_{lt_i}
clti; then, will
t
i
l
t
i
t_{\frac{i}{lt_i}}
tlti?i times plus
i
i
The number of times i can be used.
Finally, every prime number
i
i
i’s
c
i
c_i
ci? is the degree of this prime number.
The time complexity is
O
(
n
)
O(n)
O(n).
code
#include<bits/stdc + + .h>
using namespace std;
const int N=1e7;
int n,fl=0,z[N + 5],p[N + 5],lt[N + 5];
long long ans=0,c[N + 5],t[N + 5];
void init(){<!-- -->
for(int i=2;i<=N;i + + ){<!-- -->
if(!z[i]){<!-- -->
p[ + + p[0]]=i;lt[i]=i;
}
for(int j=1;j<=p[0] & amp; & amp;1ll*i*p[j]<=N;j + + ){<!-- -->
z[i*p[j]]=1;
lt[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
int main()
{<!-- -->
// freopen("factorial.in","r",stdin);
// freopen("factorial.out","w",stdout);
init();
scanf("%d", & amp;n);
for(int i=n;i>=2;i--){<!-- -->
t[i] + =n + 1-i;
c[lt[i]] + =t[i];
t[i/lt[i]] + =t[i];
t[i]=0;
}
printf("f(%d)=",n);
for(int i=1;i<=p[0];i + + ){<!-- -->
if(c[p[i]]){<!-- -->
if(fl) printf("*");
else fl=1;
if(c[p[i]]==1) printf("%d",p[i]);
else printf("%d^%lld",p[i],c[p[i]]);
}
}
return 0;
}