# 「POJ-2891」Strange Way to Express Integers-扩展欧几里德

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, \cdots , ak. For some non-negative m, divide it by every ai (1 \leq i \leq k) to find the remainder ri. If a1, a2, \cdots , ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

POJ-2891

# Math