zoj3167------------Find 7 Faster Than John Von Neumann 大數乘法

It was said that when testing the first computer designed by von Neumann, people gave the following problem to both the legendary professor and the new computer: If the 4th digit of 2^n is 7, what is the smallestn? The machine and von Neumann began computing at the same moment, and von Neumann gave the answer first.

Now you are challenged with a similar but more complicated problem: If the K-th digit of M^n is 7, what is the smallest n?

Input

Each case is given in a line with 2 numbers: K and M (< 1,000).

Output

For each test case, please output in a line the smallest n.

You can assume:

1. The answer always exist.
2. The answer is no more than 100.

Sample Input

3 2
4 2
4 3      

Sample Output

15
21
11      

大數乘法，一個數組存要乘的數，一個數組存結果，一個用來傳遞中間量

代碼：

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int K,M,n,w;
    int m[1000],m1[3],t[1000];
    while(cin>>K>>M)
    {
        memset(m,0,sizeof(m));
        memset(m1,0,sizeof(m1));
        m[0]=1;
        for(int i=0;M!=0;i++)
        {
            m1[i]=M%10;
            M=M/10;
        }         
        n=0;
        while(1)
        {
            memset(t,0,sizeof(t));
			   for(int i=0;i<=2;i++)
            {
                for(int j=0;j<1000;j++)
                {
                    t[j+i]=t[j+i]+m[j]*m1[i];
                }    
                for(int j=0;j<1000;j++)
                {
                    if(t[j]>9)
                    {
                        t[j+1]=t[j+1]+t[j]/10%10;
                        t[j]=t[j]%10;
						  }
                }
            }
            for(int j=0;j<1000;j++)
            	m[j]=t[j];
            n++;
            if(m[K-1]==7)
            {
                cout<<n<<endl;    
                break;
            }
        }            
    }
    return 0;
}