KGP14J - Editorial

[darkshadows]

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

Maths

PROBLEM:

Given X and Y, find smallest E such that Y occurs as a prefix of X^E. For example, Y ∈ {6,65,656,6561} are prefix of 3⁸.

EXPLANATION:

We will iterate over E and if we naively do the power for each E, complexity will be higher. So, we need to quickly find the first K(<10) digits of X^E, given X and E.

We write,
log₁₀{X^E} = E log₁₀{X}.
Let’s say E log₁₀{X} = 10*a + b ie. b is the decimal part in it.
Therefore, X^E = 10^{10*a + b}. Not that 10*a part contributes zeroes only, so we need only fractional part.
So, if we need first K digits of X^E, we do 10^b * 10^K-1.

For example, we need to find first 5 digits of X=2013²⁰¹³.
X = 10^{6650.637518850862} = 10⁶⁶⁵⁰ * 10^{0.637518850862}.
Note that 10⁶⁶⁵⁰ only contributes zeroes to X and not actuall digits.
So, first 5 digits will be integer part of 10^{0.637518850862} * 10⁴ = 43402.

SOLUTIONS:

Editorialist’s solution