KGP14J Editorial (Different Approach)

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.

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)

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

This solutions works but the space complexity would be high and will take a little more time the original editorial solution.