百练OJ树根问题：数学原理与C++高效实现

1. 百练OJ平台与树根问题概述

百练OJ是北京大学程序设计课程配套的在线评测系统，主要面向算法与数据结构的学习者。这个平台收录了大量经典编程题目，按照难度和类型进行分类，其中"树根"问题编号为2764，属于模拟类基础题型。

树根（Digital Root）在数学上是指一个数的各位数字持续相加直到结果为个位数的过程。例如数字9875的树根计算过程为：9+8+7+5=29 → 2+9=11 → 1+1=2，最终树根为2。这个问题看似简单，但在实际编程实现时需要处理大数输入、边界条件等细节。

2. 问题分析与数学原理

2.1 树根的数学定义

给定一个正整数n，其树根dr(n)可以通过以下两种等价方式定义：

1. 递归求和：将n的各位数字相加，如果结果大于9则继续相加，直到得到个位数
2. 模9运算：dr(n) = 1 + (n - 1) % 9 （注意n=0时的特殊情况）

数学上可以证明，一个数的树根等于该数模9的余数（当余数为0时树根为9，除非原数本身就是0）。这个性质源自10^k ≡ 1 (mod 9)的数学特性。

2.2 输入输出要求

百练OJ 2764题的具体要求：

• 输入：每行一个正整数n（0 ≤ n ≤ 10^1000），输入以n=0结束
• 输出：对每个n输出其树根
• 时间限制：C/C++ 1000ms
• 内存限制：256MB

关键挑战在于处理超大整数（最大可达1001位），无法直接用基本数据类型存储。

3. C++实现方案

3.1 字符串处理法

对于超大整数，最稳妥的方法是使用字符串存储并逐位处理：

cpp复制#include <iostream>
#include <string>
using namespace std;

int digitalRoot(string num) {
    while(num.size() > 1) {
        int sum = 0;
        for(char c : num) {
            sum += c - '0';
        }
        num = to_string(sum);
    }
    return num[0] - '0';
}

int main() {
    str