0
$\begingroup$

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.

$\endgroup$
22
  • $\begingroup$ 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? $\endgroup$ – gnasher729 Apr 8 at 14:22
  • 1
    $\begingroup$ Please credit the original source of all copied material. See cs.stackexchange.com/help/referencing. $\endgroup$ – D.W. Apr 8 at 19:57
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 8 at 19:57
  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Apr 8 at 19:57
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. Apr 8 at 19:59
1
$\begingroup$

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<p_2<\ldots<p_k$ 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.
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Loc Truong Apr 9 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.