/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
414 の十進法での表記は 414 であり、これは回文です。
また、414 の八進法での表記は 636 であり、これも回文です。
これを踏まえて、以下の問題を解いてください。
正の整数 A, N が与えられます。 1 以上 N 以下の整数のうち、十進法での表記も A 進法での表記も回文であるようなものの総和を求めてください。
なお、この問題の制約下で答えは 2^{63} 未満であることが証明できます。
制約
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- 入力される数値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
A N
出力
答えを 1 行で出力せよ。
入力例 1
8 1000
出力例 1
2155
条件を満たす整数は 1,2,3,4,5,6,7,9,121,292,333,373,414,585 の 14 個であり、その総和は 2155 です。
入力例 2
8 999999999999
出力例 2
914703021014
入力例 3
6 999999999999
出力例 3
283958331810
Score : 350 points
Problem Statement
The decimal representation of 414 is 414, which is a palindrome.
Also, the octal representation of 414 is 636, which is also a palindrome.
Based on this, solve the following problem.
You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.
Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.
Constraints
- 2 \leq A \leq 9
- 1 \leq N \le 10^{12}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A N
Output
Output the answer in one line.
Sample Input 1
8 1000
Sample Output 1
2155
The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.
Sample Input 2
8 999999999999
Sample Output 2
914703021014
Sample Input 3
6 999999999999
Sample Output 3
283958331810