CF468C Hack it
题面
给定正整数 \(n\)，求一组 \((l,r)\)，使得 \(l\) 到 \(r\) 内所有整数的数位和的和是 \(n\) 的倍数。\(n<=10^{18}\)
分析
设 \(f(i)\) 表示 \(i\) 的数位和
则显然有：\(f(i+10^{18})=f(i)+1\)
不妨设 \(\sum_{i=1}^{10^{18}-1}f(i)\equiv p (\bmod a)\) ，那么有：
\[\begin{align*}
\sum_{i=1}^{10^{18}}&=f(10^{18}+0)+\sum_{i=1}^{10^{18}-1}f(i) \&=1+f(0)+p\&\equiv p+1 (\bmod a)
\end{align*}
\]
同理，\(\sum_{i=2}^{10^{18}+1}=f(10^{18}+1)+\sum_{i=1}^{10^{18}}f(i)-f(1)\equiv p+2(\bmod a)\)
可知 \(\sum_{i=x}^{10^{18}+x-1}\equiv p+x(\bmod a)\)
那么有：
\(\sum_{i=a-p}^{10^{18}+a-p-1}\equiv p+a-p \equiv 0(\bmod a)\)
所以 \(l=a-p ,r=a-p-1\)
现在的问题是如何快速地求到 \(p\)
设函数 \(F(x)=\sum_{i=0}^{10^x-1}f(i)\) ，那么有
\[\begin{equation}
F(x)=
\left\{
\begin{array}{lr}
45,&(x=1)\ 45\times10^{x-1}+10\times F(x-1),&(x>1)
\end{array}
\right.
\end{equation}
\]
可以这样理解，\(45=1+2+3+\dots+8+9\) 是对于首位枚举
而后面的数位和不变，算上本身有需要加 \(10\) 次
最后化简得到：\(F(18)=9\times9\times10^{18}\)
代码
#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);
}