题解 CF468C 【Hack it!】

2019-07-24 16:25:21


神仙构造题?

首先可以发现,当 $x<10^{18}$ 时有这样一个关系式 $$ f(x+10^{18})-f(x)=1 $$ 也就是说,当 $[l,r]$ 从 $[1,10^{18}]$ 变成 $[x+1,x+10^{18}]$ 时, $\sum\limits_{i=l}^rf(i)$ 增加了 $x$ 。

设 $\sum\limits_{i=1}^{10^{18}}f(i)=q$ ,显然一组合法的 $[l,r]$ 为 $[a-q+1,a-q+10^{18}]$ 。

现在考虑怎么求出 $q$ 。通过打表可以发现 $\sum\limits_{i=1}^{10^x}f(i)=45x\cdot 10^{x-1}+1$ 。

那么 $q=81\times 10^{18}+1$ 。

代码