解法の方針

以下の方針で解くことができます．

1. \(1\) 以上 \(N\) 以下の整数のうち，十進法での表記が回文であるもの (以下「十進回文数」と呼ぶ) を列挙する．
2. 上で挙げた整数のそれぞれについて，\(A\) 進法での表記が回文かどうかを判定し，回文であれば答えに加える．

回文となる整数の列挙

十進回文数を観察すると，「上半分を固定すると下半分も自動的に決まる」という特徴があることがわかります．

ということは，\(d\) 桁の十進回文数を列挙するには，冒頭 \(\lceil d/2 \rceil\) 桁の部分を列挙し，そこから下半分を復元すれば十分です．ここで \(\lceil d/2 \rceil\) とは，\(d\) が偶数のとき \(d/2\) で，奇数のとき \((d+1)/2\) で求まる整数です．

注意点として，十進表記の先頭にゼロがつかないように，冒頭 \(\lceil d/2 \rceil\) 桁の部分の列挙は \((1, 0, \dots, 0)\) から始める必要があります．

\(d\) 桁の回文数を探索するにあたって列挙するべき上半分の種類は高々 \(10^{\lceil d/2 \rceil}\) 通りなので，列挙は \(O(d 10^{\lceil d/2 \rceil})\) の時間で実行できます．

回文判定

以下のようにして，\(x\) が \(A\) 進回文数かを判定することができます．

1. \(x\) の \(A\) 進数での表記を求め，下の位から \(x_0, \cdots, x_{d'-1}\) とおく．
2. すべての \(i = 0, \cdots, d'-1\) に対して，\(x_i = x_{d'-1-i}\) が成り立つかを判定する．

これは \(O(\log_A x)\) 時間で実行できます．

以上の解法を組み合わせることで，全体の時間計算量は \(O(\sqrt{N} \log N)\) となり，十分高速です．

なお，条件を満たす整数は最大でも \(64\) 個 (\(A=6\), \(N=10^{12}\) のとき) しか存在しないので，\(\text{(答え)} < 64 \times 10^{12} < 2^{63}\) がいえます．

実装例

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::pair;
using std::vector;
using std::min;
using std::max;
using std::array;
#include <atcoder/all>

typedef long long int ll;

ll a, b, n;

// determine if x is palindromic in base b
bool ispal (ll x, ll b) {
	vector<ll> s;
	// s[i] is the digit in i-th place
	while (x > 0) {
		s.push_back(x % b);
		x /= b;
	}

	bool isok = true;
	for (ll i = 0; i < s.size(); i++) {
		if (s[i] != s[s.size() - 1 - i]) isok = false;
	}
	return isok;
}
void solve () {
	b = 10;
	
	vector<ll> vec; // list of answers

	vector<ll> powb = {1}; // powb[i] == 10**i
	ll len = 1;
	while (true) {
		// extend powb enough
		while (powb.size() < len) {
			ll w = powb[powb.size()-1] * b;
			powb.push_back(w);
		}
		if (powb[len-1] > n) break;

		vector<ll> d((len+1)/2, 0); // upper half. d[0] is the most-significant-digit.
		d[0] = 1; // starts at (1, 0, ..., 0)
		while (true) {
			// calculate the palindromic integer corresponding to d as sum
			ll sum = 0;
			for (ll i = 0; i < len; i++) {
				ll idx;
				if (i < d.size()) {
					idx = i;
				} else {
					idx = (len-1) - i;
				}
				sum += powb[i] * d[idx];
			}
			// check if (sum <= n) and (sum is palindromic in base A)
			if (sum <= n) {
				bool isok = ispal(sum, a);
				if (isok) {
					vec.push_back(sum);
				}
			}

			// next d
			bool hasnext = false;
			for (ll i = d.size()-1; i >= 0;i--) {
				if (d[i] == b-1) {
					d[i] = 0;
					continue;
				} else {
					d[i] += 1;
					hasnext = true;
					break;
				}
			}
			if (!hasnext) break;
		}

		len++;
	}

	// calculate sum
	ll allsum = 0;
	for (ll v : vec) {
		allsum += v;
	}
	cout << allsum << "\n";
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> a;
	cin >> n;

	solve();

	return 0;
}