Zero Trailing Factorial

We need compute

$$\sum_{x=1}^{n-1} f_m(x,n).$$

For a fixed $x<n$, factorial valuations are monotone:

$$v_k(x!)\le v_k(n!).$$

So if the two values are different, then

$$w_k(x,n)=v_k(x!).$$

That removes one annoying branch. We are minimizing $v_k(x!)$ over all bases $2\le k\le m$ such that $v_k(n!)>v_k(x!)$.

The main trick is to count levels instead of values:

$$\sum_x f_m(x,n)=\sum_{q\ge 0} \#\{x: f_m(x,n)>q\}.$$

So we need to understand when $f_m(x,n)>q$.

Rewriting the condition

For any base $k$, the statement $v_k(x!)\le q$ and $v_k(n!)>v_k(x!)$ is equivalent to saying that some new copy of $k$ appears between $x!$ and $n!$ before we exceed level $q$.

A cleaner way:

$$f_m(x,n)>q$$

means there is no base $k\le m$ with

$$v_k(x!)\le q < v_k(n!).$$

That is the same as:

For every $k\le m$, if $k^{q+1}\mid n!$, then $k^{q+1}\mid x!$.

Because $v_k(y!)\ge q+1$ exactly means $k^{q+1}\mid y!$.

So for each $q$, define $L_q$ as the smallest $x$ such that:

$$\forall k\le m,\quad k^{q+1}\mid n! \Rightarrow k^{q+1}\mid x!.$$

Then all $x\ge L_q$ pass this condition, and all smaller $x$ fail it. Therefore

$$\#\{1\le x<n: f_m(x,n)>q\}=n-L_q$$

if $L_q<n$, otherwise $0$.

Thus the answer is

$$\sum_{q\ge 0} (n-L_q).$$

Only finitely many $q$ matter, since even $2^{q+1}\mid n!$ eventually stops being true.

How to compute $L_q$

Factor a base $k$:

$$k=\prod p^{e_p}.$$

Then

$$k^{q+1}\mid y!$$

means

$$v_p(y!)\ge (q+1)e_p$$

for every prime $p\mid k$.

The condition over all $k\le m$ can be decomposed into requirements on prime powers. If a base $k$ contains $p^e$, then $p^e\le k\le m$. So every relevant exponent requirement comes from some prime power $p^e\le m$.

For fixed $q$, prime power $p^e$ matters if

$$v_p(n!)\ge (q+1)e.$$

Then any valid $x$ must satisfy

$$v_p(x!)\ge (q+1)e.$$

For each prime $p$, we only need the largest such $e$ with $p^e\le m$ and $(q+1)e\le v_p(n!)$. Call the resulting required exponent

$$need_p(q)=(q+1)e.$$

Then $L_q$ is the smallest $x$ such that every prime requirement is satisfied:

$$v_p(x!)\ge need_p(q)$$

for all relevant primes $p$.

For a single prime requirement $v_p(x!)\ge r$, we can binary search the smallest $x$. The global $L_q$ is just the maximum over all primes, because all requirements must hold at once.

Important detail: why prime powers are enough

Suppose some composite base $k\le m$ makes a requirement. Pick any prime power $p^e\mid k$. Since $p^e\le k\le m$, our enumeration includes it. If $k^{q+1}\mid n!$, then $v_p(n!)\ge (q+1)e$, so this prime-power requirement is recorded. If $x!$ satisfies all recorded prime-power requirements, it satisfies every prime requirement needed by every such composite $k$.

So composites do not need special handling. Nice little jailbreak from factoring every base.

Bounding the work

We have $n,m\le 10^7$. Precompute primes up to $10^7$ once with a sieve.

For one test case:

• for every prime $p\le n`, compute$v_p(n!)$;
• enumerate powers $p^e\le m$;
• for each $e$, it contributes to all $q$ with $(q+1)e\le v_p(n!)$;
• update $L_q$ using the smallest $x$ with $v_p(x!)\ge (q+1)e$.

The maximum relevant $q$ is $v_2(n!)-1$, about $10^7$, but the number of useful updates is much smaller:

$$\sum_{p\le n}\sum_{e\le \log_p m}\left\lfloor\frac{v_p(n!)}{e}\right\rfloor$$

This is fine for the constraints when implemented tightly. The rating says 2400, not “please write a PhD thesis.”

To make the per-prime binary searches fast, for a fixed prime $p$ process required values in increasing order and binary search only on $[last,n]$. Since the required valuation increases, the minimal $x$ never decreases.

Finally, after all updates:

$$ans=\sum_{q\ge 0} \max(0,n-L_q).$$

Initialize $L_q=1$. Requirements only raise it. If no base has $(q+1)$ copies inside $n!$, then $L_q$ will not matter because no contribution should remain; in practice we only sum over $q$ that received at least one update.

Complexity

The sieve is $O(M\log\log M)$ for $M=10^7$.

Each test case does roughly the total number of relevant prime-power level updates, with a small logarithmic factor from binary search. This passes in C++ with normal optimization.