I completely messed up this one. Wasted 2.5 hours on the first problem getting nowhere, the program always giving wrong answers (I probably messed up the recursions…). Coded the second problem with this algorithm:
Make an array containing the positive divisors of n (doable in O(sqrt(n)) and sort them (O(d(n) log d(n)). Now let the number of aperiodic sequences of length m be given by f(m). Note that any periodic binary string of length n must have its minimal period dividing n, so there are a total of sum f(d), d|n, d<n periodic sequences of length n, and hence, 2^n - sum f(d), d|n, d<n aperiodic sequences of length n. We can compute this recursively (f(1)= 2) in O(d(n)^2).
This algorithm gave the correct answer for small integers (I had about 5 minutes left at this time). Then I quickly replaced the ints by long long ints, but didn’t get time to compile/debug my code finally. Just after exiting the hall, I recalled that I had made a map from int to int which stores the values of 2^n mod m for all n < 150000. Before submitting, I didn’t change this to a map from long long int to long long int, and also forgot to declare it outside int main. I guess I’m getting a 0 in this exam.
EDIT: Judging by the comment below, I still might have a chance! Thanks, neotech!