• 游客,您好! Include社区于2021.5.26迁移至新版社区,用户数据丢失,欢迎注册! 补偿政策

教程 [P4942] 小凯的数字 题解

Include社区

Include社区信息发布
管理成员
超级版主
2021/05/26
9
2
101
China

题目描述​

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

代码​

C++:
#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;

}



author@RMOlives
 
最后编辑:

中国

⁢⁢⁢⁢⁢⁢⁢⁢⁢⁢⁢⁢
管理成员
站长
超级版主
版主
创始会员
2021/06/04
2,147,483,647
2,147,483,647
2,147,483,667
100

在线会员

现在没有会员在线。