help needed in ASIA AMRITA ICPC REGIONAL 2016 on problem influence on social media

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 https://www.codechef.com/problems/AMR16C

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