Posted on 10th April 2015
I found this to be somewhat harder than round A. Also, my solutions in Python, running on my 2013 era laptop, are rather slow, so really a C++ or similar implementation would be needed, especially on 2008 era hardware.
Again, The Official Contest Analysis is a good writeup, so I won't say a great deal. See the code on GitHub.
Problem A: Once you realise the trick, this is a simple combinatorial problem! (And solvable easily in Python).
Problem B: In the end, I went with a "disjoint union" data structure, as in the official writeup. My implementation in Python uses a dictionary, and is hence a bit more general than necessary (and so probably slower). Also need a prime sieve to find the primes efficiently. I did experiment with forming a graph and finding components, but this seemed very slow.
Problem C: I will admit to looking at the official solutions for a hint for the "large" case. My version uses the clever, third, idea. Again, slow in Python.