【AtCoder】ABC 460 E - x + y ≡ x + y

2026-06-08

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D 競技プログラミング

E - x + y ≡ x + y

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1362 / NoviSteps: 1D / 配点: 450 点

問題概要

正整数 $a,b$ に対して、 $a$ と $b$ を文字列と見なしてこの順に連結して書いた時に出来る整数を $\mathrm{concat}(a, b)$ と呼ぶことにする。

正整数 $N, M$ が与えられるとき、 $N$ 以下の正整数の組 $(x,y)$ であって $\mathrm{concat}(x, y) \equiv x + y \pmod{M}$ であるものの個数を $998244353$ で割った余りを求めよ。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1 \leq T \leq 10^4$
$1 \leq N \leq 10^{18}$
$2 \leq M \leq 10^9$
入力される値は全て整数

考察

とりあえず、問題条件を数式で表してみる。 $y$ の桁数を $d$ とすると、

\begin{align} \mathrm{concat}(x, y) &\equiv x + y \pmod{M} \notag \\ x \cdot 10^d + y &\equiv x + y \pmod{M}\notag \\ x (10^d - 1) &\equiv 0 \pmod{M} \end{align}

となる。

式 $(1)$ より, 求める条件は $x$ と $d$ についてのみ依存することが分かる。

ここで、 $1 \leq y \leq N \leq 10^{18}$ であることから $d$ は最大で $19$ なので、以下では $d$ を固定したときの $x$ の条件について考えることにしよう。

$d$ を固定したときの $x$ の個数

式 $(1)$ を以下のように言い換える。なお、 $a \mid b$ は $b$ が $a$ の倍数であることを表す。

\begin{equation} M \mid x(10^d - 1) \end{equation}

今は $x$ に関する条件を考えているので、右側を $x$ だけで表したい。そこで、 $A = 10^d - 1$ として $g = \gcd(M, A)$ を考えると、 $M = g M'$ と $A = g A'$ と表せる。すると、式 $(2)$ は以下のように変形できる。

\begin{align*} M \mid x A & \iff g M' \mid x \cdot g A' \notag \\ & \iff M' \mid x \cdot A' \notag \\ \end{align*}

$M'$ と $A'$ は互いに素であるため、 $M'$ の素因数は全て $x$ 側に含まれていなければならない。したがって、

\begin{equation} M' \mid x \iff \left. \dfrac{M}{\gcd(M, 10^d - 1)} \right| x \end{equation}

が成り立つ。

式 $(3)$ より、 $L_d = \frac{M}{\gcd(M, 10^d - 1)}$ とおくと、 $x$ は $1 \leq x \leq N$ を満たす $L_d$ の倍数であるから、ある $d$ における条件を満たす $x$ の個数 $c_x(d)$ は、 $\left\lfloor \frac{N}{L_d} \right\rfloor$ と計算できる。

桁数が $d$ となるような $y$ の個数

$y$ の桁数が $d$ であるための条件は、 $10^{d - 1} \leq y < 10^d$ である。

しかし、これに加えて $1 \leq y \leq N$ も満たす必要があるため、 $y$ の桁数が $d$ であるような $y$ の個数 $c_y(d)$ は、

c_y(d) = \max \left( 0, \min(N, 10^d - 1) - 10^{d - 1} + 1 \right)

と計算できる。

以上より、求める答えは以下のように計算できる。

\sum_{d = 1}^{19} c_x(d) \cdot c_y(d) \pmod{998244353}

実装上の注意点

今回の方針だと $d$ は最大 $19$ まで登場するので、 $10^{19}$ がlong long 型だとオーバーフローしてしまう。そこで、 $10^d$ や $c_y(d)$ を __int128_t 型で計算する必要がある。

また、 $L_d$ の式における $\gcd(M, 10^d - 1)$ の計算については、

\gcd(M, 10^d - 1) = \gcd(M, 10^d - 1 \bmod M)

が成り立つことを踏まえると、 ACL のpow_modを用いることによって long long 型のまま計算できる。

実装例

ACLのmod_intを使ってみたが、却ってごちゃごちゃしてしまった。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
10. 
11.using ll = long long;
12.using mint = modint998244353;
13. 
14.// ======================================== //
15. 
16.using i128 = __int128_t;
17.constexpr int MOD = 998244353;
18. 
19.ll solve() {
20.    ll N, M;
21.    cin >> N >> M;
22. 
23.    vector<i128> pow10(20);
24.    pow10[0] = 1;
25.    repe(i, 1, 19) {
26.        pow10[i] = pow10[i - 1] * 10;
27.    }
28. 
29.    mint ans = 0;
30. 
31.    repe(d, 1, 19) {
32.        i128 right = min<i128>(N, pow10[d] - 1);
33.        i128 cnt_y = max<i128>(0, right - pow10[d - 1] + 1);
34. 
35.        if (cnt_y == 0) continue;
36. 
37.        ll r = (pow_mod(10, d, M) - 1 + M) % M;
38.        ll g = gcd(M, r);
39. 
40.        ll Ld = M / g;
41.        ll cnt_x = N / Ld;
42. 
43.        ans += mint((ll)(cnt_y % MOD)) * mint(cnt_x % MOD);
44.    }
45. 
46.    return ans.val();
47.}
48. 
49.int main()
50.{
51.    int T;
52.    cin >> T;
53. 
54.    while (T--)
55.    {
56.        cout << solve() << endl;
57.    }
58. 
59.    return 0;
60.}