User Tools

Site Tools


contest_2011-09-27

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
Last revisionBoth sides next revision
contest_2011-09-27 [2011/09/25 12:42] jtkorbcontest_2011-09-27 [2011/09/27 06:02] jtkorb
Line 15: Line 15:
   * 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]]   * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1045|Euclid Problem]]
-  * F: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1080|Factovisors]] +  * F: [[Prelude to Factovisors]] 
-  * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=1030|Repackaging]]+  * 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.
Line 26: Line 27:
   * 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.   * 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 GCD algorithm given in the text solves this problem directly. +  * E: The Extended Euclid Algorithm for GCD (given in the text), given in the text, solves this problem directly. 
-  * F: 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. +  * 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: Use the Diophantine solution method in the text.+  * 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.
contest_2011-09-27.txt · Last modified: 2011/09/27 11:00 by jtkorb