z3475 的博客

题解 P4942 【小凯的数字】

引理1

$$\forall x,k\in\mathbb{Z},x*10^k\%9=x\%9$$

证明(如果你不觉得显然的话):

$10\%9=1$

$10^k\%9=1$

$x*10^k\%9=x\%9$

Solution

题目中的$$l(l+1)(l+2)(r-1)r\%9$$

等价于$$(\sum_{i=l}^{r}i*10^{k})\%9$$ k不好写出来

由引理得其等价于$$(\sum_{i=l}^{r}i)\%9$$ 由等差数列求和公式得$$(l+r)*(r-l+1)/2\%9$$ 由因$$2*5\equiv 1(mod\ 9)$$ 得$$(l+r)*(r-l+1)*5\%9$$ 化简$$(l+r)\%9*(r-l+1)\%9*5\%9$$

Program

#include <iostream>
long long l,r;
int main(){
    int q;scanf("%d",&q);
    while (q--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",(l+r)%9*(r-l+1)%9*5%9);
    }
}

2018-11-02 12:25:44 in 题解