contest_2011-09-27

### Table of Contents

# Weekly Contest for September 27, 2011

## Join the Contest

% cd your-pc2-directory % /homes/cs390cp/pc2/bin/pc2team &

Log in using your individually assigned “teamX” account and password. You can work in the current window/directory, creating a subdirectory for each problem.

## Problems

- G: Factovisors
- H: Repackaging

*Remember:* If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++). If you want to work on an additional problem from the book, let me know.

**Hints:**

- A: Find a pattern. The solution is extremely short and efficient.
- B: Repeated divisions is fine (be sure to skip even numbers after 2 and only test as large as necessary).
- C: Observe that, if
`k`

is even,`n ^ k mod p`

is`(n ^ (k/2) mod p) ^ 2 mod p`

. Generalize and handle the case for`k`

odd. - D: Combine the two preludes.
- E: The Extended Euclid Algorithm for GCD (given in the text), given in the text, solves this problem directly.
- F: Brute force factorization is fine. You'll want to keep a table of
`(p,e)`

pairs for each prime,`p`

, that divides`e`

times. - G: Theorem: The highest power of
`p`

that divides`n!`

is`n/p + n/p^2 + n/p^3 …`

. So,`p^e`

divides`n!`

if this sum is at least`e`

before`n/p^k`

reaches 0. - H: The text suggests using the Diophantine solution method given there. Note that you don't actually need to compute the solution, just determine whether or not a solution exists.

contest_2011-09-27.txt · Last modified: 2011/09/27 11:00 by jtkorb