PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
We are given that the answer will have fewer than 700 digits (the maximum is actually 613). It suffices to find all solutions to the equation 2a3b5c7d=P(mod 1000000007), subject to a/3+b/2+c+d<700. To do this, we first make a list of all values Q such that 2a3b=Q(mod 1000000007) has a solution with a/3+b/2<700. We sort this list, so we can perform fast searches on it using binary search. Now for all possible values c and d with c+d<700 we check if 5-c7-dP is in our sorted list. If so, we’ve found a potential solution to the problem. Given candidate values of a, b, c, and d, we compute the answer by greedily taking as many 9’s as possible, then as many 8’s as possible, and so on, down to 2. Note that the digit 1 is never used, except when P itself is 1 or 0.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.