Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: zhouzixiang2004
Hint 1
Pure brute force should have a very hard time finding a solution. Try to get some intuition about what a valid 
~n~ would look like.
Hint 2
Let 
~n = p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}~ be its prime factorization. Rewrite 
~d(\varphi(n)) = \varphi(d(n))~ as 
~d\left((p_1-1)(p_2-1) \dots (p_k-1)p_1^{e_1-1}p_2^{e_2-1} \dots p_k^{e_k-1}\right) = \varphi\left((e_1+1)(e_2+1) \dots (e_k+1)\right)~. For now, it seems hard to control both the left and right side if we consider varying 
~e_i~. Can we restrict the search space to make it easier?
Hint 3
For now, consider ~n~ such that every prime factor occurs only once (i.e. 
~e_i = 1~).
Hint 4
We need 
~d((p_1-1)(p_2-1) \dots (p_k-1)) = \varphi(2^k) = 2^{k-1}~. Intuitively, the left side is almost always larger than the right side, especially since we cannot use 
~p_i-1 = 1~. How should the prime factors of 
~p_i-1~ relate to each other if we want to keep 
~d((p_1-1)(p_2-1) \dots (p_k-1))~ small?
Hint 5
We should consider using primes 
~p_i~ such that ~p_i-1~ only contains small prime factors, e.g. only 
~2~ and 
~3~.
Hint 6
Trying to find an ~n~ by hand is tedious and prone to only finding a large ~n~. However, we are allowed to use computer assistance.
Hint 7
Write a recursive backtracking program that tries all ~n~ under 
~10^{18}~ where ~n~'s prime factors ~p_i~ are all distinct and ~p_i-1~ only contains small prime factors. This should quickly find many large solutions for ~n~. If we search for smaller ~n~, we should be able to find two values of ~n~ with 
~13~ digits beginning with 
~12???????????~, which gets 
~80\%~ of the points.
Hint 8
The key intuition needed is that we should consider using primes ~p_i~ such that ~p_i-1~ only contains small prime factors. Recall that we restricted ourselves to using only ~e_i = 1~ earlier. Modify the recursive backtracking program to consider ~n~ where some prime factors occur more than once (
~e_i > 1~). We should be able to find a value of ~n~ with 
~11~ digits beginning with 
~15?????????~, which gets 
~100\%~ of the points.
Answer
Two intended ~n~ for ~80\%~ of the points are 
~1244586078645 = 3 \cdot 5 \cdot 7 \cdot 13 \cdot 19 \cdot 37 \cdot 73 \cdot 109 \cdot 163~ and 
~1294951381815 = 3 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 19 \cdot 37 \cdot 163 \cdot 487~.
The intended ~n~ for full points is 
~15230439315 = 3^6 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 37 \cdot 73~.
Comments
Is there another valid value for
that's smaller than 
, and if there isn't, is there a proof that 
is the lowest odd 
that satisfies 
?
wagwan