ARC129C 题解

· · 题解

首先 \text{7777...777}（x 个 7）对能被 7 整除子串数量的贡献是 \frac{x(x+1)}{2}。

把 n 分解成若干 x_i 使得 \sum\limits_{i=1}^m \frac{x_i(x_i+1)}{2} = n，表示每段 x_i 个 7。怎么把它们组合在一起呢？

一个 naive 的想法是 \text{77...77a77...77a}，其中 a 为指定的数。发现怎么指定，中间都会串出一段 7 的倍数。

既然不能指定，那么就随机好了！随机得出每段 7 之间间隔的数，直到合法就输出，可过。

code