|Online Judge||Problem Set||Authors||Online Contests||User|
In the ancient work Sunzi Suanjing (Master Sun’s Mathematical Manual), the problem below was mentioned.
Sunzi wrote in his work, “The answer is twenty-three.”
In 1592, Dawei Cheng put the solution to the problem as a poem in Suanfa Tongzong (Systematic Treatise on Arithmetic).
In modern notation, Sunzi’s problem is to find a number x such that
x ≡ 2 (mod 3),
And Cheng’s solution is
x ≡ 2 × 70 + 3 × 21 + 2 × 15 ≡ 233 (mod 105).
The solution also indicates that if one is given three integers r1, r2, r3 and is asked to find a number x such that
x ≡ r1 (mod 3),
then the answer is
x ≡ r1 × 70 + r2 × 21 + r3 × 15 (mod 105).
For example, for r1 = 1, r2 = 4, r3 = 4, the answer is
x ≡ 1 × 70 + 4 × 21 + 4 × 15 ≡ 214 (mod 105).
In generalization, given n positive integers a1, a2, …, an, the problem is to determine whether there exist n positive integers b1, b2, …, bn such that for any positive integer N, let pi (1 ≤ i ≤ n) be the remainder of N taken modulo ai and M = p1 × b1 + p2 × b2 + … + pn × bn, then M ≡ pi (mod ai) for all i (1 ≤ i ≤ n); and to find a set of values of b1, b2, …, bn if they exist.
The input consists of multiple test cases. Each test case is given in one line. In each test case, given first is the integer n (1 ≤ n ≤ 10), which is followed by a1, a2, …, an (ai ≤ 50, 1 ≤ i ≤ n). The last case, with n = 0, indicates the end of input and should not be processed.
For each test case, output one line. If the positive integers b1, b2, …, bn exist, output them (none of them should be longer than 50 decimal digits) separated by single spaces. If there are multiple answers, output any one. Output “NO” if they do not exist.
3 3 5 7 0
70 21 15
Mind your program’s output format since special judge is used.
PKU Local 2006, kicc
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator