[COCI 2019/2020 #1] Trol

GitHub跳转原题关系图返回列表

把区间和转成数根前缀和，利用数根序列以 9 为周期循环。

OJ: luogu

题目 ID: P7199

难度:普及-

标签:数学模拟

日期: 2026-06-18 21:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

原序列满足 A_i = i。 现在把每个数不断替换成数位和，直到只剩下一位数。 对每个询问 [l, r]，要求输出这一段最终值的总和。

思路

先看一个可以直接验证想法的朴素解：

逐个枚举区间里的数，对每个数反复做数位和，再累加。

cpp
#include <bits/stdc++.h>
using namespace std;

unsigned long long digit_root(unsigned long long x) {
    while (x >= 10) {
        unsigned long long sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        x = sum;
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        unsigned long long l, r;
        cin >> l >> r;
        unsigned long long ans = 0;
        for (unsigned long long x = l; x <= r; x++) {
            ans += digit_root(x);
        }
        cout << ans << '\n';
    }

    return 0;
}

真正的关键是认出这里的最终值其实就是“数根”。 正整数的数根序列按下面的模式循环：

text
1,2,3,4,5,6,7,8,9,1,2,3,...

所以每 9 个数的贡献固定是 45。

设前缀和为 S(x)，那么：

text
S(x) = (x / 9) * 45 + 1 + 2 + ... + (x % 9)

这样区间答案就能直接写成：

text
S(r) - S(l - 1)

代码

cpp
#include <bits/stdc++.h>
using namespace std;

unsigned long long prefix_sum(unsigned long long x) {
    unsigned long long block = x / 9;
    unsigned long long rem = x % 9;
    return block * 45 + rem * (rem + 1) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        unsigned long long l, r;
        cin >> l >> r;
        cout << prefix_sum(r) - prefix_sum(l - 1) << '\n';
    }

    return 0;
}

复杂度

每个询问 O(1)O(1)，总时间复杂度 O(Q)O(Q)，空间复杂度 O(1)O(1)。

总结

这题的关键不是数位和本身，而是发现“最终结果是数根，而且按 9 周期循环”。