CF468C Hack it! 题解

题意：给出一个数 \(a\)，构造一组 \(l,r\) 使得 \(\sum_{i=l}^r f(i) \equiv 0 \pmod a\)。其中 \(a \leq 10^{18}\)，\(l,r\leq 10^{200}\)。

分析：

以下用 \((l,r)\) 表示构造出来的一对 \(l,r\)，\(f(l,r)=\sum_{i=l}^r f(i)\)。

考虑从某个值一步一步移动到模 \(a\) 余 \(0\) 的情况。如果选择 \((0,9)\)，发现 \(f(1,10)=f(0,9)+1\)。这很好理解，\(f(1,10)\) 相当于 \(f(0,9)-f(0)+f(10)\)，\(10\) 比 \(0\) 的最高位多 \(1\)，所以使得 \(f(1,10)=f(0,9)+1\)。一直从 \(f(0,9)\) 推到 \(f(9,19)\) 都是这种情况，但是 \(f(10,20) \neq f(9,19)+1\)，因为 \(19\) 发生了进位，导致两边低位的变化不同。如果将十位的 \(1\) 移至足够高的数位，就能在移动区间的时候不发生进位。

所以，一开始我们选择 \((0,10^{18}-1)\)，因为 \(a \leq 10^{18}\)，区间至多右移 \(10^{18}\) 次，不会发生进位。不难发现，现在需要移动的步数就是 \(a-f(0,10^{18}-1) \ \% \ a\)。通过简单的计算，得到 \(f(0,10^{18}-1)=45 \times 18 \times 10^{17}=81 \times 10^{18}\)，于是答案为 \((81 \times 10^{18} \ \% \ a,10^{18}-1+81 \times 10^{18} \ \% \ a)\)。