Palindromic in both bases

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.

Solving

枚举十进制回文数的前半部分，分奇数和偶数的回文构造，

奇数则为省略掉后导数字再接上原数字反转后的数，偶数则直接接上反转后的数字，上述操作使用字符串操作完成，随后得到的数进行判断是否满足a进制下回文即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


void solve()
{
    int a,n;
    cin >> a >> n;
    auto check = [&](int x,int a) -> bool
    {
        string ans = "";
        int temp;
        while(x > 0)
        {
            temp = x;
            temp %= a;
            ans += to_string(temp);
            x /= a;
        }
        string rev = ans;
        reverse(ans.begin(),ans.end());
        return rev == ans;
    };
    int ans = 0;
    for(int i=1;i<=1e6;i++)
    {
        string s = to_string(i);
        string rev = s;
        reverse(rev.begin(),rev.end());
        // case 1 : ignore the last integer
        string s2 = s.substr(0,s.size()-1);
        int case1 = stoll(s2 + rev);
        if(case1 <= n and check(case1,a)) ans += case1;
        // case 2 : do not ignore
        int case2 = stoll(s + rev);
        if(case2 <= n and check(case2,a)) ans += case2;
    }
    cout << ans << endl;
}