Need help in generalization of formula

Revision en2, by deepwork, 2018-06-21 17:15:45

Problem was solved!

Input is consist of 1 ≤ q ≤ 2 * 104 queries every of which are described with single positive integer n not exceeding 4 * 106.
Output is to print for each query:

x⌋ =  whole part of number, i.e. max integer which's  ≤ x
φ(x) is Euler Totient Function

OK, I can previously calculate phis of all numbers from 1 to 4 * 106 and P i for any i, 1 ≤ i ≤ 4 * 106 in O(nlogn), but what's then? I don't know how to further optimize solution, because it is TLE with O(n) complexity per query.
Please, help me!

Tags math, number theory, phi, help me please


  Rev. Lang. By When Δ Comment
en2 English deepwork 2018-06-21 17:15:45 47 Tiny change: 'which's $\ge x$ \n ' -> 'which's $\le x$ \n '
en1 English deepwork 2018-06-20 14:25:09 722 Initial revision (published)