题解 CF468C 【Hack it!】

· · 题解

思考过程极为巧妙。

我们首先考虑一个数字x，若f(x)=y，则f(x+10^{18})=f(x)+1=y+1. 这是很显然的事情。

我们设\sum_{i=0}^{10^{18}-1}f(i)\equiv p ~(\!\!\mod\! a~)，则

\sum_{i=1}^{10^{18}}f(i). =f(10^{18}+0)+\sum_{i=1}^{10^{18}-1}f(i). =1+f(0)+\sum_{i=1}^{10^{18}-1}f(i). =1+\sum_{i=0}^{10^{18}-1}f(i)\equiv p+1 ~(\!\!\mod\! a~).

同样，我们可以推出

\sum_{i=2}^{10^{18}+1}f(i)\equiv p+2 ~(\!\!\mod\! a~). \sum_{i=3}^{10^{18}+2}f(i)\equiv p+3 ~(\!\!\mod\! a~). .... \sum_{i=r}^{10^{18}+r-1}f(i)\equiv p+r ~(\!\!\mod\! a~). .... \sum_{i=a-p}^{10^{18}+a-p-1}f(i)\equiv p+a-p ~(\!\!\mod\! a~).

即\sum_{i=a-p}^{10^{18}+a-p-1}f(i)\equiv 0 ~(\!\!\mod\! a~).

所以l=a-p,r=10^{18}+a-p-1时，满足条件。

可见，我们主要的事情是求出p，即\sum_{i=0}^{10^{18}-1}f(i).

注意到

\sum_{i=0}^{10^{18}-1}f(i) =45\times 10^{17}+10\times \sum_{i=0}^{10^{17}-1}f(i) =45\times 10^{17}+10\times (45\times 10^{16})+100\times \sum_{i=0}^{10^{16}-1}f(i) =.... =18\times 45\times 10^{17} =81\times 10^{18}.

即p=81\times 10^{18} \!\mod a.

于是就可以愉快的AC掉本题啦！

#include<cstdio>
typedef long long LL;
LL l,r,inf=1e18,mod;
int main(){
    scanf("%lld",&mod);
    l=mod-inf%mod*9%mod*9%mod;
    r=l+inf-1;
    printf("%lld %lld\n",l,r);
}