DMOPC '21 Contest 10 P5 - Number Theory

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Find an odd integer n with 1 < n < 10^{18} such that d(\varphi(n)) = \varphi(d(n)).

For any positive integer m,

  • \varphi(m) is the number of integers between 1 and m inclusive that are coprime to m.
  • d(m) is the number of positive divisors of m.

Input Specification

There is no input for this problem.

Output Specification

Output n.


If your output is improperly formatted, n is even, or n does not satisfy 1 < n < 10^{18} and d(\varphi(n)) = \varphi(d(n)), you will receive 0 points.

Otherwise, your score will be \min(5 \cdot (37-\lceil \log_4(n) \rceil),100). For full points, n must be less than 4^{17}.

Sample Output



Note that d(\varphi(6)) = d(2) = 2 and \varphi(d(6)) = \varphi(4) = 2, so this value of n satisfies d(\varphi(n)) = \varphi(d(n)).

Unfortunately, this value of n is not odd, so it would score 0 points.


There are no comments at the moment.