how to prove that the Every supporter is of the form p^{q-1} , where p , q are primes and q is odd.
problem link AMR16C Problem - CodeChef
Proving it is simple.
The condition is that the number of divisors must be an odd prime number.
Write P_i in its prime factorization form. Notice that if P_i is of form {p_1}^{a}*{p_2}^{b}...., then number of divisors is (a+1)*(b+1)... and hence NEVER prime (since it is a product of some numbers).
\implies That for number of divisors of P_i to be prime, it should be expressible in terms of a single prime number.
1 Like