题解 CF468C 【Hack it!】
Nemlit
2019-10-15 17:07:30
构造题果然都非常神仙啊
~~首先翻译有点问题,$L, R$的范围应该为$[1, 10^{200}]$~~
由于模数a达到了$10^{18}$,所以我们可以发现,当$i<10^{18}$时,$f()$有一个性质:
$$ f(i+10^{18}) = f(i)+1$$
我们令$g=\sum_{i=1}^{10^{18}}f(i)\ (mod\ a)$
于是我们有:$g+1=\sum_{i=2}^{10^{18}+1}f(i)\ (mod\ a)$
$g+a-g=\sum_{i=a-g+1}^{10^{18}+a-g}f(i)\ (mod\ a)=0\ (mod\ a)$
所以我们可以构造出一组解为$[a-g, 10^{18}+a-g+1]$
于是我们现在问题就变成了求出$g$
$g=\sum_{i=1}^{10^{18}-1}f(i)+1$
对于$10^{18}-1$的所有数位出现次数都是一样长的
所以答案应该为$45*$每一个数位出现多少次
这个东西就可以用~~数位DP~~组合数来求了:我们把原问题想象成:有18个空位,你可以放$[0, 9]$中的所有数,问$i$放了多少次
$$ans=\sum_{i=1}^{18}C_{18}^i*9^{18-i}$$
然后用$__int128$跑一下,答案为$45*18*10^{17}+1=81*10^{18}+1$
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
long long a, pax = 1e18 + 1;
signed main() {
cin >> a;
long long l = a - pax % a * 9 % a * 9 % a, r = pax + l - 1;
printf("%lld %lld", l, r);
return 0;
}
```