题解 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 ```cpp #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); } } ```