{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eThere are a lot of mysteries and legends around computer science. One of the stories tells us about three Russian hackers who know the secret of breaking down widely used cryptographic algorithm. The fact itself threatens security of economics of many countries. Until recent time nobody knew anything about these hackers but now federal security bureau knows their names (Roman, Sergey and Andrew) and they also know that their hack method somehow uses discrete roots finding algorithm. And of course nobody knows this algorithm. We suggest you to try to solve much simpler task. \u003cbr\u003eGiven two prime numbers P and K (2 \u0026lt;\u003d P \u0026lt;\u003d 10^9, 2 \u0026lt;\u003d K \u0026lt;\u003d 100000) and integer number A (0 \u0026lt;\u003d A \u0026lt; P) you are to find all the roots of the equation x^K \u003d A mod P. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eInteger numbers P, K, A. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThe first line of output should contain number of roots of the equation. On the second line all the roots should be listed in ascending order. \u003cbr\u003eNote: all the roots should be in the range [0..P-1]. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e11 3 8 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e1 \u003cbr\u003e2 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eIgor A. Kulkin \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003eSaratov SU Contest: Golden Fall 2004 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eOctober 2, 2004 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}