問題: AtCoder ABC 238 C — digitnum · English · 한국어
1からNまでのすべての整数について、10進表記の桁数を合計し、998244353で割った余りを出力します。
整数を桁数ごとにまとめます。桁数がdの整数の範囲は[10^(d-1), min(N, 10^d - 1)]です。この範囲に含まれる整数の個数にdを掛け、答えに加算します。範囲の終端がNに達したら繰り返しを終了します。
桁数の範囲はO(log N)個なので、時間計算量はO(log N)、追加の空間計算量はO(1)です。範囲の端点はlongで計算します。10^dを求める際のオーバーフローを避けるため、次の10の累乗がN以下であることを確認してから10倍します。
Java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static final long MOD = 998244353L;
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(input.readLine().trim());
long answer = 0;
long start = 1;
for (long digits = 1; start <= n; digits++) {
long end = n;
if (start <= n / 10) {
end = start * 10 - 1;
}
long count = end - start + 1;
answer = (answer + (digits % MOD) * (count % MOD)) % MOD;
if (end == n) {
break;
}
start *= 10;
}
System.out.println(answer);
}
}