시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 161 46 39 33.051%

문제

믿기 힘들겠지만 상근이는 이번 겨울 방학에 달에 갔다 왔다. 방학이 끝나고 다시 학교로 돌아온 상근이는 친구들에게 달나라 사람(Selenites)을 만났던 이야기를 해주었다.

상근이는 달에서 사용하는 수 체계를 주로 설명해주었다. 달에서는 음의 진법을 사용한다.

음의 진법은 사람들이 이해하기는 어렵다. 따라서, 상근이는 달을 여행하는 동안 0과 \(n\)을 포함하는 사이의 수 중에서 \(k\)진법과 \(-k\)진법에서 표현이 같은 수를 모두 외웠다. 상근이가 외운 숫자의 개수를 구하는 프로그램을 작성하시오.

\(x\)의 \(k\)진법 표현은 0 ≤ \(a_i\) < \(\left| k  \right| \), \(\sum_{i = 0} ^ {p} {a_i \times k^i} = x\)를 만족하는 수열 \(a_0\),\(a_1\),...,\(a_p\)이다.

입력

첫째 줄에 \(n\)과 \(k\)가 주어진다. (1 ≤ \(n\) ≤ 1015, 2 ≤ \(k\) ≤ 1,000)

출력

첫째 줄에 상근이가 달에서 생활하면서 외운 숫자의 개수를 출력한다.

예제 입력 1

21 3

예제 출력 1

9

예제 입력 2

21 2

예제 출력 2

8

힌트

첫 번째 예제에서 상근이는 0, 1, 2, 9, 10, 11, 18, 19, 20을 외웠다.

19는 3진법과 -3진법에서 19 = 2013 = 201-3 으로 표현이 같다. 하지만, 7은 7 = 213 = 111-3 으로 같지 않다.

두 번째 예제의 경우에는 0, 1, 4, 5, 16, 17, 20, 21을 외우면 된다.

W3sicHJvYmxlbV9pZCI6IjM5OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MDRcdWIzMDBcdWQ1NWMgXHVjMGFjXHVhZTMwXHVhZmJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmZcdWFlMzAgXHVkNzk4XHViNGU0XHVhY2EwXHVjOWMwXHViOWNjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWJjODggXHVhY2E4XHVjNmI4IFx1YmMyOVx1ZDU1OVx1YzVkMCBcdWIyZWNcdWM1ZDAgXHVhYzE0XHViMmU0IFx1YzY1NFx1YjJlNC4gXHViYzI5XHVkNTU5XHVjNzc0IFx1YjA1ZFx1YjA5OFx1YWNlMCBcdWIyZTRcdWMyZGMgXHVkNTU5XHVhZDUwXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyOCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNWQwXHVhYzhjIFx1YjJlY1x1YjA5OFx1Yjc3YyBcdWMwYWNcdWI3OGMoU2VsZW5pdGVzKVx1Yzc0NCBcdWI5Y2NcdWIwYWNcdWIzNTggXHVjNzc0XHVjNTdjXHVhZTMwXHViOTdjIFx1ZDU3NFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlY1x1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjMjE4IFx1Y2NiNFx1YWNjNFx1Yjk3YyBcdWM4ZmNcdWI4NWMgXHVjMTI0XHViYTg1XHVkNTc0XHVjOGZjXHVjNWM4XHViMmU0LiBcdWIyZWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNzRjXHVjNzU4IFx1YzljNFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc0Y1x1Yzc1OCBcdWM5YzRcdWJjOTVcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc3NFx1ZDU3NFx1ZDU1OFx1YWUzMFx1YjI5NCBcdWM1YjRcdWI4MzVcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlY1x1Yzc0NCBcdWM1ZWNcdWQ1ODlcdWQ1NThcdWIyOTQgXHViM2Q5XHVjNTQ4IDBcdWFjZmMgXFwoblxcKVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXFwoa1xcKVx1YzljNFx1YmM5NVx1YWNmYyBcXCgta1xcKVx1YzljNFx1YmM5NVx1YzVkMFx1YzExYyBcdWQ0NWNcdWQ2MDRcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjNjc4XHVjNmUwXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNjc4XHVjNmI0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlxcKHhcXClcdWM3NTggXFwoa1xcKVx1YzljNFx1YmM5NSBcdWQ0NWNcdWQ2MDRcdWM3NDAgMCAmbGU7IFxcKGFfaVxcKSAmbHQ7IFxcKFxcbGVmdHwgayAmbmJzcDtcXHJpZ2h0fCBcXCksIFxcKFxcc3VtX3tpID0gMH0gXiB7cH0ge2FfaSBcXHRpbWVzJm5ic3A7a15pfSZuYnNwOz0geFxcKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNWY0IFxcKGFfMFxcKSxcXChhXzFcXCksLi4uLFxcKGFfcFxcKVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAmbmJzcDtcXChuXFwpXHVhY2ZjIFxcKGtcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFxcKG5cXCkgJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCAyICZsZTsgXFwoa1xcKSAmbGU7IDEsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjJlY1x1YzVkMFx1YzExYyBcdWMwZGRcdWQ2NWNcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNjc4XHVjNmI0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMCwgMSwgMiwgOSwgMTAsIDExLCAxOCwgMTksIDIwXHVjNzQ0IFx1YzY3OFx1YzZlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MTlcdWIyOTQgM1x1YzljNFx1YmM5NVx1YWNmYyAtM1x1YzljNFx1YmM5NVx1YzVkMFx1YzExYyAxOSA9IDIwMTxzdWI+MzxcL3N1Yj4gPSAyMDE8c3ViPi0zPFwvc3ViPiBcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVjNzc0IFx1YWMxOVx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCA3XHVjNzQwIDcgPSAyMTxzdWI+MzxcL3N1Yj4gPSAxMTE8c3ViPi0zPFwvc3ViPiBcdWM3M2NcdWI4NWMgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDAsIDEsIDQsIDUsIDE2LCAxNywgMjAsIDIxXHVjNzQ0IFx1YzY3OFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JlYXQgRGVjZWl2ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPk9uY2UgdXBvbiBhIHRpbWUgQmFyb24gTXVuY2hoYXVzZW4gdHJhdmVsZWQgdG8gdGhlIE1vb24uIEFmdGVyIHRoYXQgaGUgb2Z0ZW4gdGVsbHMgaW50ZXJlc3Rpbmcgc3RvcmllcyBhYm91dCB0aGUgU2VsZW5pdGVzLiBSZWNlbnRseSBCYXJvbiB0b2xkIHVzIGFib3V0IHRoZWlyIG51bWVyaWMgc3lzdGVtLiBUaGV5IHVzZSBhIG5vdGF0aW9uIHdpdGggbmVnYXRpdmUgcmFkaXghPFwvcD5cclxuXHJcbjxwPk5lZ2F0aXZlIHJhZGl4IGlzIHF1aXRlIGhhcmQgZm9yIEh1bWFucywgYW5kIGV2ZW4gZm9yIE11bmNoaGF1c2VuLiBTbywgQmFyb24gZGlkIGEgdHJpY2sgdG8gaGVscCBoaW1zZWxmIG9uIHRoZSBNb29uLiBIZSByZW1lbWJlcmVkIGFsbCB0aGUgbnVtYmVycyBiZXR3ZWVuIDAgYW5kIG4gaW5jbHVzaXZlbHksIHdoaWNoIGhhdmUgdGhlIHNhbWUgbm90YXRpb24gZm9yIGJvdGggU2VsZW5pdGVzJnJzcXVvOyBuZWdhdGl2ZSByYWRpeCAmbWludXM7ayBhbmQgYSBtb3JlIGNvbnZlbmllbnQgcG9zaXRpdmUgcmFkaXggay48XC9wPlxyXG5cclxuPHA+TXVuY2hoYXVzZW4gY2xhaW1zIHRoYXQgaGUgZGlkIHRoYXQgZWFzaWx5LiBCdXQsIHlvdSBrbm93LCBCYXJvbiBjYW4gZXhhZ2dlcmF0ZSBhIGxpdHRsZS4gVG8gY2F0Y2ggaGltLCB5b3UgaGF2ZSB0byBjb3VudCBob3cgbWFueSBudW1iZXJzIGhlIG11c3QgaGF2ZSByZW1lbWJlcmVkLjxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgay1yYWRpeCBub3RhdGlvbiBvZiBhIG51bWJlciB4IGlzIGEgc2VxdWVuY2Ugb2YgaW50ZWdlcnMgYTxzdWI+MDxcL3N1Yj4sIGE8c3ViPjE8XC9zdWI+LCAuLi4sIGE8c3ViPnA8XC9zdWI+IHN1Y2ggdGhhdCAwICZsZTsgYTxzdWI+aTxcL3N1Yj4mbmJzcDsmbHQ7IHxrfCZuYnNwO2FuZCAmc3VtO2E8c3ViPmk8XC9zdWI+Kms8c3VwPmk8XC9zdXA+Jm5ic3A7PSB4IChpPTB+cCk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBzaW5nbGUgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBuIGFuZCBrICgxICZsZTsgbiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4sIDIgJmxlOyBrICZsZTsgMSAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgbnVtYmVycyBCYXJvbiBNdW5jaGhhdXNlbiBtdXN0IGhhdmUgcmVtZW1iZXJlZCBkdXJpbmcgaGlzIHN0YXkgb24gdGhlIE1vb24uPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBcdWZiMDFyc3Qgc2FtcGxlLCBCYXJvbiBtdXN0IGhhdmUgcmVtZW1iZXJlZCBudW1iZXJzIDAsIDEsIDIsIDksIDEwLCAxMSwgMTgsIDE5IGFuZCAyMC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIDE5IGhhcyB0aGUgc2FtZSBub3RhdGlvbiBmb3IgYm90aCByYWRpeCAzIGFuZCByYWRpeCAmbWludXM7MzogMTkgPSAyMDE8c3ViPjM8XC9zdWI+ID0gMjAxPHN1Yj4mbWludXM7MzxcL3N1Yj4sIHdoaWxlIDcgaGFzIG5vdDogNyA9IDIxPHN1Yj4zPFwvc3ViPiA9IDExMTxzdWI+Jm1pbnVzOzM8XC9zdWI+PFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgc2FtcGxlLCB0aGUgY29ycmVzcG9uZGluZyBudW1iZXJzIGFyZSAwLCAxLCA0LCA1LCAxNiwgMTcsIDIwIGFuZCAyMS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northeastern European Regional Contest > NEERC 2012 G번