NUC1015 计算数字的根

计算数字的根

时间限制: 1000ms 内存限制: 65536KB

问题描述

每个正整数通过每一位的求和都可以找到一个对应的根值.如果求和的结果是一位数字,那么这个数字就是这个正整数的根,如果这个值是两位或多位的话,重复上面的求和,直到求和结果为一位数字.

例如:考虑正整数24.把2和4相加得到6.6是一个数字,那么6就是24的根.现在考虑正整数39,3+9=12,12不是一位数.那么重复相加1+2=3,所以得到3为39的根.

现给定数据求该数的根.

输入描述

输入数据第一行有一个正整数N,表示下边有N个数据要计算.接下来分别是N行需要求根的正整数m. 其中( 1 ≤ m ≤ 10⁵⁰ )

注:10⁵⁰表示10的50次方

输出描述

输出这N个正整数的根,每个根占一行.

样例输入

3

24

39

987654321

样例输出

6

3

9

问题分析：

输入的数有50位，没法用整数类型存储，只能用字符串存储。

程序说明：

一般的做法是把各位数字加起来，加着加着数就变大了，需要迭代计算和的各位数字之和，直到剩下1位数。

利用数论的９余数定理来计算数根，则不需要这种迭代。

参见链接博文。

参考链接：HDU1013 POJ1519 Digital Roots（解法三）

AC的C++程序如下：

#include <iostream>

using namespace std;

int main()
{
    int n, digitroot;
    string s;

    cin >> n;
    while(n--) {
        cin >> s;

        digitroot = 0;
        int i =0;
        while(s[i]) {
            digitroot += s[i] - '0';
            digitroot = digitroot % 9;
            i++;
        }

        cout << ((digitroot == 0) ? 9 : digitroot) << endl;
    }

    return 0;
}