CF468C Hack it! 题解

题目链接：Hack it!

题意：

小 X 最近遇到了下面的问题。

我们定义函数 $f(x)$ 为 $x$ 的各个数位之和。

比如说，$f(1234)=1+2+3+4=10$。任务是，计算 $\sum_{i=l}^rf(i)\bmod a$​ 的值。

小 X 很快就解决了这个问题。于是小 X 锁定了这道题，然后开始 hack 别人。他看到了下面这段代码：

ans = solve(l, r) % a;
if (ans <= 0) ans += a;

显而易见地，这段代码会在 $\sum_{i=l}^rf(i)\equiv 0 \pmod a$ 时输出错误。

小 X 会告诉你题目中的 $a$​ 是多少，现在请你为小 X 构造一个 hack 数据。

输入格式：

输入包括一行，即小 X 给定的 $a$ 的值（$1\le a\le 10^{18}$）。输入保证有解。

输出格式：

输出两个整数：$L,R$，满足 $1\leq L\leq R\leq 10^{200}$，同时 $\sum_{i=l}^rf(i)\equiv 0 \pmod a$，即你构造的 hack 数据。

非常巧妙的题，建议先做这道题 P2602 [ZJOI2010] 数字计数

设 $\sum_{i=0}^{10^{18}-1} f(i) \equiv p \pmod{a}$ ，则

$$\begin{aligned} \sum_{i=0}^{10^{18}-1} f(i) &\equiv f(10^{18} + 0) + \sum_{i=0}^{10^{18}-1} f(i) \\[6pt]&\equiv1 + f(0) + \sum_{i=1}^{10^{18}-1}f(i) \\[6pt]&\equiv p + 1 \pmod{a} \end{aligned}$$

同理，我们可以得到

$$\begin{aligned} & \sum_{i=2}^{10^{18}+1} f(i) \equiv p+2 \pmod{a} \\[6pt]& \sum_{i=3}^{10^{18}+2} f(i) \equiv p+3 \pmod{a} \\[6pt]& \quad\cdots\cdots \\[6pt]& \sum_{i=r}^{10^{18}+r-1} f(i) \equiv p+r \pmod{a} \\[6pt]& \quad\cdots\cdots \\[6pt]& \sum_{i=a-p}^{10^{18}+a-p-1} f(i) \equiv p+a-p \pmod{a} \end{aligned}$$

最后一行显然 $p+a-p \equiv 0 \pmod{a}$ 。

那么我们只需要求出 $p$ 即可，即 $\sum_{i=0}^{10^{18}-1} f(i)$​。

$$\begin{aligned} \sum_{i=0}^{10^{18}-1} f(i) & = 45 \times 10^{17}+10 \times \sum_{i=0}^{10^{17}-1} f(i) \\[6pt]&= 45 \times 10^{17}+10 \times\left(45 \times 10^{16}\right)+100 \times \sum_{i=0}^{11^{16}-1} f(i) \\[6pt]&= \cdots\cdots \\[6pt]&= 18 \times 45 \times 10^{17} \\[6pt]&= 81 \times 10^{18} \end{aligned}$$

于是这题就做完啦！

时间复杂度 $\mathcal{O}(1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

const int p = 1e18;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int a, l, r; cin >> a; 
    l = a - p % a * 9 % a * 9 % a; r = l + p - 1;
    cout << l << ' ' << r;
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/cfuugfja