호석이와 태규는 4와 7을 행운의 숫자라고 여겼다. 그래서 그들은 10진수로 표현할 때 4와 7로만 구성되어 있는 수를 행운의 수라고 부른다.
최근에 호석이와 태규는 10진법이 아닌 B진법에 대해 공부를 하고 흥미를 느꼈다. B진법에는 0부터 B-1 사이의 서로 다른 B개의 수로 구성되어있다.
자연수 A를 B진법으로 나타내려면
를 만족하는 a[n],a[n-1],..,a[0]을 알아야한다.
예를 들어 B=52 일때 자연수 255를 B진법으로 표현하면 255 = 4*52 + 47이다. 십진수 255를 B진법으로 표현을 하면 숫자 4와 47로 구성되어있다.
한 십진법 자연수 A를 B진법으로 표현할 때 그 숫자가 행운의 수로만 구성되어 있으면 'B는 A에 대해 행운이다'라고 말한다.
십진법 자연수 A가 주어질 때 A에 대해 행운인 수 B의 개수를 구하자.
입력 255 출력 2 입력 474 출력 -1 입력 13 출력 0 입력 4748 출력 5
출처 : Topcoder SRM 510 Div1 Level Three 추천 : tamaki