Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414) C、E题解

C - Palindromic in Both Bases

题意：

在\([1,N]\)\((1\leq N\leq10^{12})\)中找出所有自身为回文数，且\(A\)进制数仍为回文的数字，将它们求和。

思路：

代码写的很丑陋，其实转成string类型会方便很多。
首先求回文数，再在其中求\(A\)进制回文数。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Check if x represented in base A is a palindrome
bool isPalindromeBaseA(ll x, int A) {
    vector<int> digs;
    while (x > 0) {
        digs.push_back(x % A);
        x /= A;
    }
    int i = 0, j = (int)digs.size() - 1;
    while (i < j) {
        if (digs[i++] != digs[j--]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A;
    ll N;
    cin >> A >> N;

    // Convert N to string to get its decimal length
    string sN = to_string(N);
    int maxLen = sN.size();

    ll answer = 0;

    // Generate all decimal palindromes of length L = 1..maxLen
    for (int L = 1; L <= maxLen; L++) {
        int half = (L + 1) / 2;
        ll start = (half == 1 ? 1 : (ll)pow(10, half - 1));
        ll end   = (ll)pow(10, half) - 1;

        for (ll root = start; root <= end; root++) {
            string t = to_string(root);
            string rev = t;
            // if odd length, drop the last digit of the second half
            if (L & 1) rev.pop_back();
            reverse(rev.begin(), rev.end());
            string pal_s = t + rev;

            // Parse to integer
            ll p = stoll(pal_s);
            if (p > N) break;       // further roots only make p larger
            // Check base-A palindrome
            if (isPalindromeBaseA(p, A)) {
                answer += p;
            }
        }
    }

    cout << answer << "\n";
    return 0;
}

E - Count A%B=C

题意：

Find the number, modulo \(998244353\), of integer tuples \((a, b, c)\) that satisfy the following conditions.
\(1 \leq a, b, c \leq N\)
\(a \neq b \neq c\)
\(a \bmod b = c\)

思路：

首先发现若\(a < b\)，\(a\)一定等于\(c\)，一定不满足。所以一定有\(1 \leq b < a \leq N\)，因为\(c \neq 0\)，故\(a\)一定不是\(b\)的倍数，考虑对于每一个\(b \in [1, N - 1]\)，\(a\)的填法个数，\([b + 1, N]\)中有\(N - b\)个数字，其中能整除\(b\)的有\(\lfloor \frac{N - b}{b} \rfloor\)个，故\(a\)的个数有\(N - b - \lfloor \frac{N - b}{b} \rfloor\)个。原问题变成求

\[\sum_{b=1}^{N} \left( N - b + 1 - \left\lfloor \frac{N}{b} \right\rfloor \right)\bmod MOD \]

对于前三项，使用等差数列求和公式，对于后一项，使用 数论分块

代码

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
using namespace std;

const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;
const int mod = 998244353;
//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;

ll ksm (ll a, ll b) {
	 ll res = 1;
	 while (b) {
	 	 if (b & 1) res = res * a % mod;
	 	 b >>= 1;
	 	 a = a * a % mod;
	 }
	 return res;
}
void solve() {
	 ll n;
	 cin >> n;
	 ll ans = (n % mod * ((n + 1) % mod)) % mod * ksm (2, mod - 2) % mod;
     for (ll l = 1; l <= n; ++l) {
     	 ll v = n / l;
     	 ll r = n / v;
     	 ans = (ans % mod - ((r - l + 1) % mod * v % mod) % mod + mod) % mod;
         l = r;
     }
     cout << ans << "\n";
}
int main() {
	 ios::sync_with_stdio (false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 t = 1;
	 //cin >> t;
	 while (t --) {
	 	 solve();
	 }
	 return 0;
}