×

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.

This question is marked "community wiki".

19.7k350498541
accept rate: 35%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,630
×1,341
×16
×9

question asked: 27 Nov '12, 19:23

question was seen: 1,464 times

last updated: 27 Nov '12, 19:23