Hack It!
题目描述
Little X has met the following problem recently.
Let’s define $f(x)$ as the sum of digits in decimal representation of number $x$ (for example, $f(1234)=1+2+3+4$). You are to calculate $\sum_{i=l}^r f(i) \bmod a$.
Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:
1 |
|
This code will fail only on the test with $\sum_{i=l}^r f(i) \equiv 0 \pmod a$. You are given number $a$, help Little X to find a proper test for hack.
题意概述
令$f(i)$表示$i$各位数字之和。给定$a$,要求找出一对$(l, r)$满足$\sum_{i=l}^r f(i) \equiv 0 \pmod a$。
数据范围:$1 \le a \le 10^{18}$。
算法分析
思路很巧妙。有一个显而易见的结论:$\forall i \in [1, 10^{18}], \ f(i)+1=f(i+10^{18})$。它有一个推论:$\forall x \in [1, 10^{18}], \ 1+\sum_{i=x}^{x+10^{18}-1} f(i)=\sum_{i=x+1}^{x+10^{18}} f(i)$。因此只要算出$t=\sum_{i=1}^{10^{18}} f(i) \bmod a$,将区间右移$a-t$单位。
代码
1 |
|