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 revision Previous revision
Next revision
Previous revision
contest_2011-09-27 [2011/09/25 05:31]
jtkorb
contest_2011-09-27 [2011/09/27 11:00] (current)
jtkorb
Line 11: Line 11:
  
   * A: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=35&​page=show_problem&​problem=1051|Light,​ More Light]]   * A: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=35&​page=show_problem&​problem=1051|Light,​ More Light]]
 +  * B: [[Prelude One to Carmichael Numbers -- Primality Testing]]
 +  * 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]]
 +  * 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.
Line 17: Line 24:
  
   * 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). 
 +  * 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.1316953904.txt.gz · Last modified: 2011/09/25 05:31 by jtkorb