题解 P4942 【小凯的数字】
z3475
2018-11-02 12:25:44
## 引理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);
}
}
```