Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Sunzi's Problem
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 718Accepted: 90Special Judge

Description

In the ancient work Sunzi Suanjing (Master Sun’s Mathematical Manual), the problem below was mentioned.

We have a number of things, but we do not know exactly how many. If we count them by threes we have two left over. If we count them by fives we have three left over. If we count them by sevens we have two left over. How many things are there?

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).

Three septuagenarians walking together, ’tis rare!
Five plum trees with twenty one branches in flower,
Seven disciples gathering right by the half-moon,
One hundred and five taken away, lo the result shall appear!

In modern notation, Sunzi’s problem is to find a number x such that

x ≡ 2 (mod 3),
x ≡ 3 (mod 5),
x ≡ 2 (mod 7).

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

xr1 (mod 3),
xr2 (mod 5),
xr3 (mod 7),

then the answer is

xr1 × 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 ≤ in) be the remainder of N taken modulo ai and M = p1 × b1 + p2 × b2 + … + pn × bn, then Mpi (mod ai) for all i (1 ≤ in); and to find a set of values of b1, b2, …, bn if they exist.

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 n (1 ≤ n ≤ 10), which is followed by a1, a2, …, an (ai ≤ 50, 1 ≤ in). 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 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.

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

[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