# Joseph

### From Progteam

Sorter: | Mlc413 |
---|---|

Source: | Unknown |

Link: | http://acm.pku.edu.cn/JudgeOnline/problem?id=1012 |

**Joseph** is problem number 1012 on the Peking University ACM
site.

## Siegel Insight

Rebecca received this email from Professor Siegel. See what you can make of it:

Anyhow, there is an intuitively clear partial solution, which tells us how to solve your problem. Cut 1 A sufficient M (that is not necessarily the smallest) is 2k(2k-1)(2k-2) . . . (k+1) - 1 Can you see why? Think about it. Cut 2 Smaller is the least common multiple of 2k,2k-1,2k-2, . . . (k+1) -1 . In retrospect, you have enough time (I suspect) to write all of the linear systems for all possible Ms and use the Chinese remainder theorem to solve for all of these things. The point is that although there are a zillion different solutions, this zillion is much smaller than a search through all M's (I think) The system is a bit of a p.i.a (wuzat?) but it is M congruent to a_1 mod 2k M -2k +a_1 +1 congruent to a_2 mod 2k-1 . dotdotdod mod 2k-2 . . dot dotdod mod k-1 Etc. The different systems have a_i sequencing through all cases, which are k,k+1,k+2, ... ,2k-i The place locations are counted zero through 2k-1 You have k! different systems to solve. And once you have one solution, the rest are easy to get quite quickly. Each sol is a sum of fundamental solutions (standard Chinese remainder theorem or Langrange interpolation technique.) Clear? Somewhat clear? Sort of? -AS