题目描述

小凯有一天突发奇想,写下了一串数字: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

输入格式:

第一行为数字Q,表示小凯有Q个问题
第2 - Q + 1 行,每行两个数字 l, r 表示数字范围

输出格式:

对于每行的问题输出一行,一个数字,表示小凯问题的回答

题目分析

由题目知道,就是要我们求一个位是连续自然数的数 MOD 9的结果
由弃九验算法知道,A MOD 9 = [A的每一位数之和] MOD 9 = [[A的每一位数 MOD 9]之和] MOD 9
有函数f(x) = x mod 9,因为满足f(x + T) = f(x) [其中 T = 9]知,函数f是一个周期函数
函数f一个完整的周期E = [0, 1, 2, 3, 4, 5, 6, 7, 8],其中(SUM(E) = 36) MOD 9 = 0
所以答案ANS = SUM([f(n) ∈ N | n ≥ l, n ≤ r] U [0, 1, 2, 3, 4, 5, 6, 7, 8]) MOD 9
因为A的位是连续自然数,凑不齐周期E的数都在最左边和最右边
所以我们可以从l开始一直不断加1直到第一个数X满足(X MOD 9 = 0)的数,将这些数加起来,为S1
从r开始一直不断减1直到第一个数X满足(X MOD 9 = 0)的数,将这些数加起来,为S2
于是答案ANS = (S1 + S2) MOD 9
我们可以先写出一个0 ~ 8的前缀和数组SUMS
那么S1 = 36 - SUMS[IF(l MOD 9 != 0) l MOD 9 - 1 ELSE 0]
S2 = SUMS[r MOD 9]
然后就可以计算出最终的结果
ANS = (36 - SUMS[IF(l MOD 9 != 0) l MOD 9 - 1 ELSE 0] + SUMS[r MOD 9]) MOD 9

代码

#include <stdio.h>

int main() {
    long long q, l, r;
    int sums[9] = {0, 1, 3, 6, 10, 15, 21, 28, 36};
    scanf("%lld", &q);
    while (q--) {
        scanf("%lld %lld", &l, &r);
        printf("%d\n", (36 - sums[l % 9 != 0 ? l % 9 - 1 : 0] + sums[r % 9]) % 9);
    }
    return 0;
}