You are not logged in. Please login at www.codechef.com to post your questions!

×

DIGITS - Editorial

PROBLEM LINKS

Practice
Contest

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.

This question is marked "community wiki".

asked 27 Nov '12, 19:23

admin's gravatar image

0★admin ♦♦
19.7k350498541
accept rate: 35%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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