kevinkowa's blog

Explain the proof for this problem
By kevinkowa, history, 9 years ago, In English

http://codeforces.net/problemset/problem/230/B how come the square of a prime number is a T-prime? How would you get to the conclusion of that to solve this problem?

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

We know that if N = p1a1p2a2...pnan , then number of distinct positive integers D = (a1 + 1) * (a2 + 1) * ... * (an + 1). For D = 3, we have only one possibility, that is a1 = 2 and rest all ai = 0. Hence, N is of the form p2.

→ Reply