ABC 164
Table of Contents
https://atcoder.jp/contests/abc164
A. Sheep and Wolves
https://atcoder.jp/contests/abc164/tasks/abc164_a
B. Battle
https://atcoder.jp/contests/abc164/tasks/abc164_b
C. gacha
https://atcoder.jp/contests/abc164/tasks/abc164_c
D. Multiple of 2019
https://atcoder.jp/contests/abc164/tasks/abc164_d
2026/1/22 解説 AC
あまりでまとめる系の問題だということを知った状態で解いたが自力では解けなかった。
https://kenkoooo.com/atcoder/#/contest/show/bd593eb7-d83c-479e-a99d-d6242eff88ea?activeTab=Problems
$S$ を10進数の整数とみなす。
$l$ 桁目から $r$ 桁目までを抜き出して10進数としてみたときの数を $f(l, r)$ とすると
$f(0,r) - f(0,l-1) = f(l,r) \times 10^{l-1}$
となる。ここで $f(0, 0) = 0$ とする。
$10^x$ と $2019$ は互いに素なので、$f(l,r)$ が 2019 の倍数であるとき、$f(0,r) - f(0,l-1)$ も 2019 の倍数となる。
よって $f(0,i)$, $i \in [1, N]$ の $2019$ で割ったあまりが同じものの組を数え上げれば良い。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
reverse(all(S));
ll mod = 2019;
vll ms(mod);
ll sum = 0;
ms[0] = 1;
ll N = S.size();
ll ten = 1;
rep(i, N) {
sum += (S[i] - '0') * ten;
sum %= mod;
ten *= 10;
ten %= mod;
ms[sum]++;
}
ll ans = 0;
rep(m, mod) {
ll x = ms[m];
ans += x * (x - 1) / 2;
}
cout << ans << endl;
}
E. Two Currencies
https://atcoder.jp/contests/abc164/tasks/abc164_e