Joseph

From Progteam

Revision as of 08:12, 23 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search



Joseph
Problem Number 1012
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
Personal tools