BZOJ2405 数字

题面

bzoj2405.png

题解

首先发现 $D(x)$ 就是不停地求 $x$ 的每一位上数字之和直到其变为一个一位数
然后 $D(x)$ 有没有简单的表示方法
设数 $x$ 有 $n$ 位,第 $i$ 位为 $a_i$
则 $x$ 可以表示为 $\sum_{i=0}^{n-1} a_i\times 10^i$
再观察 $D(x)$ 即为 $\sum_{i=0}^{n-1} a_i$
此时可以发现
$$ \sum_{i=0}^{n-1} a_i\equiv \sum_{i=0}^{n-1}a_i\times 10^i \pmod{9} $$

$$ D(x)\equiv x \pmod{9} $$
所以我们推出 $D(x) =x\% 9$ ,因为最后的答案肯定是整数,所以当 $x\%9=0$ 时 $D(x)=9$
设 $x=9k+z,1\leq z\leq 9$

$$ x\cdot D(x) = 9kz+z^2 $$
所以
$$ x\cdot D(x)\equiv z^2 \pmod{9z} $$
由于$lcm(1,2,3\dots 9)\times 9 = 22680 $
所以 $x$ 与 $x + 22680$ 的情况一定相同,相当于发现了一个循环
于是预处理 $1,2,3\dots 22680$ 内的解的前缀和,设为 $sum[x]$
则当 $x > 22680$ 时有
$$ sum[x]=\lfloor \frac{x}{22680}\rfloor \cdot sum[22680] + sum[x\% 22680] $$
预处理后单个询问 $O(1)$

代码

#define P 22680
typedef long long ll;

ll L, R;
ll sum[P + 7];

inline void init () {
    int z;
    for (int x = 1; x <= P; ++x) {
        z = x % 9;
        if (z == 0) z = 9;
        if (z * x <= P)
            sum[z * x] = 1;
    }
    for (int i = 1; i <= P; ++i)
        sum[i] += sum[i - 1];
}

inline ll calc (ll x) {
    return (x / P) * sum[P] + sum[x % P];
}

int main () {
    init();
    int T;
    read(T);
    while (T--) {
        read(L), read(R);
        printf("%lld\n", calc(R) - calc(L - 1));
    }
    return 0;
}

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注