79 人解决，94 人已尝试。
128 份提交通过，共有 549 份提交。
3.6 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
RSA is a well-known algorithm for public-key encryption. It uses a number which is the product of two primes as a public-key. Usually the two primes are selected randomly, but Dr. Imo found that the number can contain more information by choosing particular primes. Of course, Dr. Imo is intelligent enough to demonstrate that the public-key of the new method is as marvelously strong as that of the older method.
The Imo method is simple. Seek the pair of primes if you are given one prime and two number.
The two primes and the two number meet the following requirements.
Thus, you can generate an RSA public-key ab which has information about c. For example, if a is 2, b is 13, c is 10 and d is 4, the remainder of division of a key 26(= ab) by 24(= 2d) includes information 10(= c).
One prime b and two numbers c, d are given. You need to find the minimum prime a to assist him.
The input is a sequence of datasets followed by a line containing three zeroes separated by a space.
A dataset is a line containing three integers b, c and d separated by a space. You may assume that b is a prime, 2 ≤ b < 221, 0 < c < 2d ≤ 220.
CAUTION!
Although the sample input contains only small datasets, note that a × b is larger than 231.
The output should be composed of lines, each corresponding to an input dataset. An output line should contain an integer indicating a prime a that meets ab ≡ c (mod 2d). You may assume that it is less than 221.
The output must be written to standard output.
13 10 4 19 7 5 0 0 0
2 29
79 人解决，94 人已尝试。
128 份提交通过，共有 549 份提交。
3.6 EMB 奖励。