# Four functions problem

This is not from online contest

Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.

## Four functions

You are given four functions \begin{align} A(x)&=\text{Number of }i\text{ where }1\leq i\leq x\text{ and }\gcd(i,x)=1\\ B(x)&=\sum_{d|x}A(d)\\ C(x)&=\text{Sum of exponents of each prime in the prime factorization of }B(x)\\ D(x)&=\sum_{i=1}^{x}C(x) \end{align}

Input:

• First line: $$T$$ [number of test cases]
• Each test case consists of an integer $$N$$

Output format

For each test case, print a single integer denoting the value of $$D(N)$$ in a new line.

Input constraints

\begin{align}1\leq T\leq 10^6\\1\leq N\leq 10^6\end{align}

Here's my observation:

• About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.

• I guess this problem is a math one. We somehow need to come up with an efficient formula to resolve all 4 functions.

• I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute gcd and prime factor.

• I've thought about this one for two days I can't find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.

Since this is a math problem, some talented and gifted genius out there might be interested. :D

Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.

• If you had a table containing the largest prime factor of x, for 1 ≤ x ≤ 1,000,000, how long would factoring any number up to 1,000,000 take? – gnasher729 Apr 8 at 14:22
• Please credit the original source of all copied material. See cs.stackexchange.com/help/referencing. – D.W. Apr 8 at 19:57
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. – D.W. Apr 8 at 19:57
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – D.W. Apr 8 at 19:57
• This looks identical to stackoverflow.com/q/62777612/781723, codereview.stackexchange.com/q/245127/65105, which claims it is from an online contest. Where did you encounter it? – D.W. Apr 8 at 19:59

Let me put together the two comments.

The function $$A$$ is Euler's totient function, which is often called $$\phi$$.

The function $$B(x)=\sum_{d|n}\phi(d)$$ is known to be equal to $$B(x)=x$$.

Now, observe that $$D(x)=\sum_{i=1}^{x}C(B(i))=\sum_{i=1}^{x}C(i)=C(x!)$$, where the last equation is because $$C$$ satisfies $$C(a)+C(b)=C(ab)$$.

Now, if $$p_1 are the primes less than or equal to $$x$$ and $$x!=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$$, then $$C(x!)=a_1+a_2+...+a_k$$

We can use Legendre's formula to compute each $$a_i$$. Note that the formula doesn't need to compute $$x!$$, but it computes $$a_i=\left\lfloor\frac{x}{p_i}\right\rfloor+\left\lfloor\frac{x}{p_i^2}\right\rfloor+\left\lfloor\frac{x}{p_i^3}\right\rfloor+\ldots$$ where there are actually finitely many summands.

So, an algorithm to compute $$D(x)$$ can be:

1. Compute the primes $$p_1,p_2,\ldots,p_k$$ up to $$x$$. This can be done using some sieve, like Erathostenes' or Atkin's
2. Then for each prime evaluate Legendre's formula above, which takes about $$\log_{p_i}(x)$$ divisions.
• Thanks, I will try implementing the solution base on your algorithm. It's interesting to know the equivalent of each function and also to know that they're easy to compute. – Loc Truong Apr 9 at 3:31