This problem already has an Editorial. You can look at Here
But I have a completely different idea with basic mathematics. Thats why iam writing a new Editorial.
PROBLEM LINK:
Practice
Contest
## 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
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 :