P4942 小凯的数字-JZTXT

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;
}