Outline of solution

The solution can be solved by the following steps.

1. Enumerate all integers between \(1\) and \(N\) whose decimal representations are palindromes. (Call these integers “decimal palindromes.”)
2. For each integer enumerate above, determine if it is also a palindrome when expressed in base \(A\), and add it to the answer if it is.

Enumerating decimal palindromes

Decimal palindromes have the following property: when you know the first half, the last half is automatically determined.

Thus, in order to enumerate \(d\)-digit decimal palindromes, it is sufficient to enumerate the prior \(\lceil d/2 \rceil\)-digit and reconstruct the later part. Here, \(\lceil d/2 \rceil\) is the integer defined as \(d/2\) if \(d\) is even and \((d+1)/2\) if odd.

Make sure to avoid having leading zeros in the decimal representations. Specifically, start the enumeration of the first \(\lceil d/2 \rceil\) digits from \((1, 0, \dots, 0)\).

Since there are \(10^{\lceil d/2 \rceil}\) combinations for the prior part of a \(d\)-digit palindrome, the enumeration can be completed in \(O(d 10^{\lceil d/2 \rceil})\) time.

Palindrome determination

One can determine if \(x\) is a palindrome in base \(A\) as follows:

1. Find the base-\(A\) representation of \(x\). Let \(x_0, \cdots, x_{d'-1}\) be the digits, from lower to upper.
2. For all \(i = 0, \cdots, d'-1\), determine if \(x_i = x_{d'-1-i}\).

This can be done in \(O(\log_A x)\).

By combining the algorithms above, the overall time complexity is \(O(\sqrt{N} \log N)\), which is fast enough.

By the way, there are at most \(64\) integers that satisfy the conditions (when \(A=6\) and \(N=10^{12}\)), so we can prove that \(\text{(answer)} < 64 \times 10^{12} < 2^{63}\)

Sample code

#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;
}