2645. Extended RSA

单点时限: 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.

  • There are two primes a, b and two number c, d (c < 2d).
  • ab ≡ c (mod 2d). ((a * b) mod (2 ** d) = c)

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.

样例

Input
13 10 4
19 7 5
0 0 0
Output
2
29

38 人解决,45 人已尝试。

61 份提交通过,共有 228 份提交。

4.1 EMB 奖励。

创建: 12 年,9 月前.

修改: 4 年,8 月前.

最后提交: 1 年,3 月前.

来源: The 1st Imos Contest

题目标签