P4942 小凯的数字

P4942 小凯的数字

题目和数据范围提示有 (O(1))作法。

直接拆数字，会TLE

$res \mod 9 = l(l + 1)(l + 2)…(r - 1)r \mod 9$

找规律不难发现 (\texttt{所有数位的数字之和} \mod 9) 即为答案。
但直接求所有数位之和明显不行，（数位dp好像可以，也许吧没试过）

观察到不需要求出所有数位的数字之和，求出所有数其自身 (\mod 9)的值之和就可以了

(res = A_{l} + A_{l + 1} + \dots + A_{r - 1} + A_{r} \mod 9)

为什么可以这样化？
(A) 的数位有 (N) 位， 有数位(A_1A_2\dots A_{N - 1}A_{N})

$A_1 + A_2 \dots A_{N - 2}A_{N - 1}A_{N} \mod 9 = A_1A_2\dots A_{N - 1}A_{N} \mod 9$

(\vdots)

(A_1A_2 \dots A_{N - 2} + A_{N - 1}A_{N} \mod 9 = A_1A_2\dots A_{N - 1}A_{N} \mod 9)
(A_1A_2 \dots A_{N - 1} + A_{N} \mod 9 = A_1A_2\dots A_{N - 1}A_{N} \mod 9)

成立

所以 (res = \sum_{i = l}^{r} i \mod 9)

师妹告诉我等差数列求和公式还可以简化式子，是我写复杂了

void solve()
{   
	ll l, r;	cin>>l>>r;
	__int128 rs = (__int128) r * (r + 1) / 2ll;
	l--;
	__int128 ls = (__int128) l * (l + 1) / 2ll;
	__int128 res = (rs - ls) % 9;
	cout<<(ll)res<<'\n';
    return;
}