U32670 小凯的数字

Description

小凯有一天突发奇想,写下了一串数字:l(l+1)(l+2)…(r-1)r
例如:l=2,r=5时,数字为:2345
l=8,r=12时数字为:89101112
小凯很喜欢数字9,所以他想问你他写下的数字除以9的余数是多少

例如:l=2,r=5时,2345 mod 9 = 5

Solution

$$
l(l + 1) (l + 2)\cdots r \pmod 9=l\bmod 9 (l + 1) \bmod 9\cdots
$$
答案为$\sum_{i = l}^ri\pmod 9$
可以利用等差数列求和公式, 但是实际上这样求会爆long long.
发现$9n\equiv 0\pmod 9$, 所以以9为周期.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <string.h>
#include <algorithm>
int sum[19];
int main () {
int n; scanf("%d", &n);
for (int i = 1; i < 9; i += 1) sum[i] = (sum[i - 1] + i) % 9;
while (n --) {
long long l, r;
scanf("%lld%lld", &l, &r);
long long len = r - l + 1;
printf("%lld\n", (sum[r % 9] - sum[(l % 9 - 1 + 9) % 9] + 9) % 9);
}
return 0;
}
-------------本文结束感谢您的阅读-------------