시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB159187817587348.353%

문제

다음과 같이 정의된 수열이 있다.

  • D[1] = A
  • D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

예제 입력 1

57 2

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjIzMzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMThcdWJjZjVcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RFsxXSA9IEE8XC9saT5cclxuXHQ8bGk+RFtuXSA9IERbbi0xXVx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBQXHViYzg4IFx1YWNmMVx1ZDU1YyBcdWMyMThcdWI0ZTRcdWM3NTggXHVkNTY5PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBBPTU3LCBQPTJcdWM3N2MgXHViNTRjLCBcdWMyMThcdWM1ZjQgRFx1YjI5NCBbNTcsIDc0KD01PHN1cD4yPFwvc3VwPis3PHN1cD4yPFwvc3VwPj0yNSs0OSksIDY1LCA2MSwgMzcsIDU4LCA4OSwgMTQ1LCA0MiwgMjAsIDQsIDE2LCAzNywgJmhlbGxpcDtdXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVhZGY4IFx1YjRhNFx1YzVkMFx1YjI5NCBcdWM1NWVcdWMxMWMgXHViMDk4XHVjNjI4IFx1YzIxOFx1YjRlNCg1N1x1YmQ4MFx1ZDEzMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2MgNThcdWJkODBcdWQxMzApXHVjNzc0IFx1YmMxOFx1YmNmNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhY2M0XHVjMThkIFx1YWQ2Y1x1ZDU1OFx1YjJlNCBcdWJjZjRcdWJhNzQgXHVjNWI4XHVjODIwXHVhYzAwIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYzE4XHViY2Y1XHVjMjE4XHVjNWY0XHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJjMThcdWJjZjVcdWI0MThcdWIyOTQgXHViZDgwXHViZDg0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzIxOFx1YzVmNFx1YzVkMCBcdWIwYThcdWFjOGMgXHViNDE4XHViMjk0IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWNcdWIyOTQgWzU3LCA3NCwgNjUsIDYxXVx1Yzc1OCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWIwYThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBBKDEgJmxlOyBBICZsZTsgOTk5OSksIFAoMSAmbGU7IFAgJmxlOyA1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCZuYnNwO1x1YmMxOFx1YmNmNVx1YjQxOFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjBhOFx1YWM4YyBcdWI0MThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjMzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxpZmUgQ3ljbGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGFyZSBjYWxjdWxhdGluZyB0aGUgJnF1b3Q7bGlmZSBjeWNsZSZxdW90OyBmb3IgZWFjaCBvZiB0aGVpciBpZGVudGlmaWNhdGlvbiB0YWcgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+VGFrZSBhbnkgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsdDs9IE4gJmx0Oz0gOTk5OSksIHNheSA1Nywgc3F1YXJlIGFsbCB0aGUgZGlnaXRzIGFuZCBhZGQgdGhlbSB1cDogJm5ic3A7NV4yICsgN14yIHRvIGdldCAyNSArIDQ5ID0gNzQuIE5vdyBkbyB0aGUgc2FtZSBwcm9jZWR1cmUgd2l0aCB0aGUgcmVzdWx0IDc0IHRvIGdldCB0aGUgbmV4dCBudW1iZXIgaW4gdGhlIHNlcXVlbmNlIDY1LiBDb250aW51aW5nIHRvIGFwcGx5IHRoaXMgcHJvY2VkdXJlIHRvIGEgc2VxdWVuY2Ugb2YgdGVybXMgZXZlbnR1YWxseSByZXBlYXRzIG9uZSBudW1iZXIgb2YgdGhlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5XaGVuIHN0YXJ0aW5nIHdpdGggNTcsIHRoZSBzZXF1ZW5jZSByZXBlYXRzIGZvciB0aGUgZmlyc3QgdGltZSB3aXRoIDM3LCB3aGljaCBpcyB0aGUgbmV4dCBudW1iZXIgaW4gdGhpcyBwYXJ0IG9mIHRoZSBzZXF1ZW5jZTo8XC9wPlxyXG5cclxuPHA+NTcsIDc0LCA2NSwgNjEsJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZyb20gdGhlbiBvbiB0aGUgc2VxdWVuY2UgaXMgdHJhcHBlZCBpbiBhICZxdW90O2xpZmUgY3ljbGUmcXVvdDs6PFwvcD5cclxuXHJcbjxwPjM3LCA1OCwgODksIDE0NSwgNDIsIDIwLCA0LCAxNiwgMzcsIC4gLiAuPFwvcD5cclxuXHJcbjxwPklmIHdlIGN1YmUgdGhlIGRpZ2l0cyBpbnN0ZWFkIG9mIHNxdWFyaW5nIHRoZW0gdGhlIHNlcXVlbmNlIGhhcyBhIHNpbWlsYXIgZmF0ZS4gWW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgaG93IGxvbmcgdGhlIHNlcXVlbmNlIGxhc3RzIHVudGlsIGl0IGZhbGxzIGludG8gYSBsaWZlIGN5Y2xlIGdpdmVuIGEgc3RhcnRpbmcgcG9zaXRpdmUgaW50ZWdlciBhbmQgYSBwb3dlciBQICgxICZsdDs9IFAgJmx0Oz0gNSkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgUC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5MZW5ndGggb2YgdGhlIHNlcXVlbmNlIHVudGlsIGl0IGVudGVycyBhIGxpZmUgY3ljbGUsIG5vdCBpbmNsdWRpbmcgdGhlIGZpcnN0IG51bWJlciBpbiB0aGUgY3ljbGUuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoaXMgY29ycmVzcG9uZHMgdG8gdGhlIHNlcXVlbmNlOiA1NywgNzQsIDY1LCA2MSwgMzcsIC4uLjsgMzcgaXMgdGhlIGZpcnN0IG51bWJlciB0aGF0IGlzIHJlcGVhdGVkLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==