### PROBLEM LINK:

**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**.

^{8}### 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 _{10}{X^{E}}** =

**E log**.

_{10}{X}Let’s say

**E log**=

_{10}{X}**10*a + b**ie.

**b**is the decimal part in it.

Therefore,

**X**=

^{E}**10**. Not that

^{10*a + b}**10*a**part contributes zeroes only, so we need only fractional part.

So, if we need first

**K**digits of

**X**, we do

^{E}**10**.

^{b}* 10^{K-1}For example, we need to find first 5 digits of **X=2013 ^{2013}**.

**X**=

**10**=

^{6650.637518850862}**10**.

^{6650}* 10^{0.637518850862}Note that

**10**only contributes zeroes to

^{6650}**X**and not actuall digits.

So, first 5 digits will be integer part of

**10**=

^{0.637518850862}* 10^{4}**43402**.