| Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision |
| contest_2011-09-27 [2011/09/25 07:11] – jtkorb | contest_2011-09-27 [2011/09/27 06:02] – jtkorb |
|---|
| * C: [[Prelude Two to Carmichael Numbers -- Efficient Power Mod]] | * C: [[Prelude Two to Carmichael Numbers -- Efficient Power Mod]] |
| * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=947|Carmichael Numbers]] | * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=947|Carmichael Numbers]] |
| | * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1045|Euclid Problem]] |
| | * F: [[Prelude to Factovisors]] |
| | * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1080|Factovisors]] |
| | * H: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1030|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 [[jtk@purdue.edu|me]] know. | //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 [[jtk@purdue.edu|me]] know. |
| * A: Find a pattern. The solution is extremely short and efficient. | * 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). | * 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)'' squared. Generalize and handle the case for ''k'' odd. | * 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. | * 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: Use the Diophantine solution method in the text. |
