题解 P4942 【小凯的数字】

ttjb · 2019-11-16 22:48:07 · 题解

这是一道很有意思的数学题，分享一下我的思路。

首先说一下一个数模 9 有什么特殊性质：

令数字 a 从左往右第 i 位数为 a_i，共 n 位，则有式一：

在加上

可以想出朴素算法1.0，根据题意将[a,b]上的所有整数拆成一位位数，然后累加求模。

然而这显然会爆 ~.~。

于是我们继续优化。

一不小心注意到式一中 等号两边交换 也是成立的。

由此可将朴素算法1.0优化一下，将[a,b]上每一个数直接累加，然后求模，得到朴素算法2.0。

然并卵，还是会爆 -_-。

但我们不要灰心，优化是无止境的。

对于每个数 p ,显然都有任意整数 n 满足式二：

也就是说，我们在枚举 [a,b] 时有很多个连续的 [kn+1,kn+9] 都是不需要管的，我们只需要特判 a 和 b 各自所在的那个 [k_xn+1,k_xn+9] 就可以了。

举个栗子：

为了方便，我们让 n=9，即 kn 是 9 的倍数，则有 a \in[10\ ,18] ， b \in[173\ ,180] ，我们取其交集，也就是 [15\ ,18]\cup[173\ ,179] ，然后把这个区间上的整数加起来模 9 就是答案。

由此得到O(1)算法3.0 了qwq。

看到这儿，你已经有办法AC这道题了，但是还是那句话，

优化是永无止境的。

在算法3.0中，n 的选取还是挺麻烦的。如果a 和 b在同一个 [n+1,\ n+9] 里时就好了，可以直接累加。

呀~这个思路貌似可行。反正中间有一大段都没用，我们能否让 a 和 b直接跳到同一区间呢？

我们可以让 b 不断减 9 ，直到 a 和 b 相遇。用循环效率太低，但是O(1)求又有点绕。这时候，相信你已经能脱口而出了：

优化是永无止境的。

实际上，让 a 不断减 9 也不会改变结果。那我们就可以直接模 9 ，很轻松地让a 和 b一下子跳到同一区间。

记得维护 a \le b。

本人才疏学浅，想到这步已经是极限了。期盼有哪位神牛能继续优化下去。

优化是永无止境的。

附上高清代码

#include<cstdio>
int main()
{
    long long a,b;
    int T,ans;  //自信地将ans定义为 int 
    for(scanf("%d",&T);T;T--)
    {
        scanf("%lld%lld",&a,&b);

        a%=9,b%=9;      //一步邂逅
        if(b<a)b+=9;    //维护 

        ans=0;
        for(int i=a;i<=b;i++)//累加 
            ans+=i;

        printf("%d\n",ans%9);
    }
    return 0;
}

后记

当我敲到这一行时，时间是是2019年11月16日 22:35:11。

今天是CSP-S 的 Day1。

脑袋在出考场后无比清醒，沮丧、悔恨、绝望···

今天已经白给了，省一的梦愈发模糊。

当初搞奥赛谁不是为了拿奖呀...

但是，如果能重来，我仍要选OI。我已经被算法的魅力深深吸引。在这说来话长的一年当中，我对OI的感情更深沉了。这也算是一场美丽的邂逅吧。

人生的相遇相逢不存在O(1)，愿每位OIer仍在路上。

还有不到10小时就是Day2了，该休息了，那就写到这里吧。