This problem already has an Editorial. You can look at Here

http://discuss.codechef.com/questions/59789/kgp14j-editorial

But I have a completely different idea with basic mathematics. Thats why iam writing a new Editorial.

# PROBLEM LINK:

# 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 38.

# EXPLANATION:

There exists a very nice algorithm to multiply a very large number (stored in array) and a small number(that lies in integer range)

You can read more about algorithm here

http://www.codechef.com/wiki/tutorial-small-factorials

Here is the pseudo code:

a[]//used to store x^e

b[]//used to store y

mx=0// used to store number of digits in x

my=0// used to store number of digits in y

//storing y in b[]..

while(y>0){

b[my++]=y%10;

y/=10;

}

// storing y complete

//storing x^0=1 intially

mx=1

a[0]=1

exp=0

while(true){

multiply x stored in array with x using above algorithm;

exp++;

//now a contains x^exp

if(y is prefix of x^exp)

ans=exp and break;

}

print ans

Here is my C++ code :

http://www.codechef.com/viewsolution/5651534

asked
**26 Dec '14, 20:58**

3★sainath_b

384●2●6●13

accept rate:
11%