[P4942] 小凯的数字 题解

题目描述

小凯有一天突发奇想,写下了一串数字: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 = \Bigg(\sum_{k \subseteq \{f(n) \in N | n \geq l, n \leq r\}}k\Bigg) \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", &amp;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;
}
本文《[P4942] 小凯的数字 题解》由 RM Olive (rmolives@gmail.com) 发布,如有版权纠纷及其他问题可以与我取得联系进行解决。

评论

  1. 喵喵喵
    Windows Chrome 88.0.4324.104
    3月前
    2021-2-02 12:25:37

    难道会 coding 的高中生不是很可爱吗?

    不!不!不!不!不…..可 爱

    • RM Olive 博主
      Linux Chrome 88.0.4324.96
      3月前
      2021-2-02 12:29:53

      超…超…超!超!超!!!!不可爱,喵喵喵最可爱了~~

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇