Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Sunzi's Problem
Description In the ancient work
Sunzi wrote in his work, “ In 1592, Dawei Cheng put the solution to the problem as a poem in
In modern notation, Sunzi’s problem is to find a number
And Cheng’s solution is
The solution also indicates that if one is given three integers
then the answer is
For example, for
In generalization, given n positive integers b_{1}, b_{2}, …, b such that for any positive integer _{n}N, let p (1 ≤ _{i}i ≤ n) be the remainder of N taken modulo a and _{i}M = p_{1} × b_{1} + p_{2} × b_{2} + … + p × _{n}b, then _{n}M ≡ p (mod _{i}a) for all _{i}i (1 ≤ i ≤ n); and to find a set of values of b_{1}, b_{2}, …, b if they exist._{n}Input The input consists of multiple test cases. Each test case is given in one line. In each test case, given first is the integer a ≤ 50, 1 ≤ _{i}i ≤ n). The last case, with n = 0, indicates the end of input and should not be processed.Output For each test case, output one line. If the positive integers Sample Input 3 3 5 7 0 Sample Output 70 21 15 Hint Mind your program’s output format since special judge is used. Source PKU Local 2006, kicc |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator