### Site Tools

contest_2011-09-27

This is an old revision of the document!

# 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

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 GCD algorithm given in the text solves this problem directly.
• F: