0%

Problem 636


Problem 636


Restricted Factorisations

Consider writing a natural number as product of powers of natural numbers with given exponents, additionally requiring different base numbers for each power.

For example, $256$ can be written as a product of a square and a fourth power in three ways such that the base numbers are different.
That is, $256 = 1^2 \times 4^4 = 4^2 \times 2^4 = 16^2 \times 1^4$.

Though $4^2$ and $2^4$ are both equal, we are concerned only about the base numbers in this problem. Note that permutations are not considered distinct, for example $16^2\times 1^4$ and $1^4\times 16^2$ are considered to be the same.

Similarly, $10!$ can be written as a product of one natural number, two squares and three cubes in two ways ($10!=42\times 5^2\times 4^2 \times 3^3 \times 2^3 \times 1^3 = 21 \times 5^2 \times 2^2 \times 4^3 \times 3^3 \times 1^3$) whereas $20!$ can be given the same representation in $41680$ ways.

Let $F(n)$ denote the number of ways in which $n$ can be written as a product of one natural number, two squares, three cubes and four fourth powers.

You are given that $F(25!)=4933$,
$F(100!) \mod 1\ 000\ 000\ 007=693\ 952\ 493$,
and $F(1\ 000!)\mod 1\ 000\ 000\ 007=6\ 364\ 496$.

Find $F(1\ 000\ 000!)\mod 1\ 000\ 000\ 007$.


有限制的因数分解

考虑将自然数表示成一系列给定指数的幂的乘积,同时要求这些幂的底数互不相同。

例如,将$256$表示成一个平方数乘以一个四次方数,且底数互不相同,有三种不同的方式,分别是
$256 = 1^2 \times 4^4 = 4^2 \times 2^4 = 16^2 \times 1^4$。

尽管$4^2$和$2^4$是相等的,但是在这个问题中我们只要求底数不同。还要注意,改变排列方式并不认为是不同的表示方式,例如$16^2\times 1^4$和$1^4\times 16^2$是相同的表示。

类似地,将$10!$表示成一个自然数、两个平方数和三个立方数的乘积,有两种方式($10!=42\times 5^2\times 4^2 \times 3^3 \times 2^3 \times 1^3 = 21 \times 5^2 \times 2^2 \times 4^3 \times 3^3 \times 1^3$),而$20!$则有$41680$种表示方式。

记$F(n)$为将$n$表示成一个自然数、两个平方数、三个立方数和四个四次方数的方式总数。

已知$F(25!)=4933$,
$F(100!) \mod 1\ 000\ 000\ 007=693\ 952\ 493$,
$F(1\ 000!)\mod 1\ 000\ 000\ 007=6\ 364\ 496$。

求$F(1\ 000\ 000!)\mod 1\ 000\ 000\ 007$。