hexo-blog/source/_posts/oi/hack-it.md

---

title: Hack It! tags:

• Constructive Algorithm id: "1706" categories:
• - OI
  • Common Skill date: 2018-01-10 09:30:20 ---

题目描述

Little X has met the following problem recently.

Let's define $f(x)$ as the sum of digits in decimal representation of number $x$ (for example, $f(1234)=1+2+3+4$). You are to calculate $\sum_{i=l}^r f(i) \bmod a$.

Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:

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

This code will fail only on the test with $\sum_{i=l}^r f(i) \equiv 0 \pmod a$. You are given number $a$, help Little X to find a proper test for hack.

题意概述

令$f(i)$表示$i$各位数字之和。给定$a$，要求找出一对$(l, r)$满足$\sum_{i=l}^r f(i) \equiv 0 \pmod a$。

数据范围：$1 \le a \le 10^{18}$。

算法分析

思路很巧妙。有一个显而易见的结论：$\forall i \in [1, 10^{18}], \ f(i)+1=f(i+10^{18})$。它有一个推论：$\forall x \in [1, 10^{18}], \ 1+\sum{i=x}^{x+10^{18}-1} f(i)=\sum{i=x+1}^{x+10^{18}} f(i)$。因此只要算出$t=\sum_{i=1}^{10^{18}} f(i) \bmod a$，将区间右移$a-t$单位。

代码

#include <cstdio>

long long mul(long long a, long long b, long long mod) {
  long long ret = 0;
  while (b) b & 1 && ((ret += a) %= mod), (a <<= 1) %= mod, b >>= 1;
  return ret;
}

int main() {
  long long n; scanf("%lld", &n);
  long long cur = mul(1800000000000000000ll, 45, n) + 1, l = 1, r = 1000000000000000000ll;
  l += n - cur, r += n - cur, printf("%lld %lld\n", l, r);
  return 0;
}