Digital Root

题目大意：有K组测试数据，然后每组有N个正整数，A1,A2,A3.....An，求出 A1 + A1*A2 + A1*A2*A3 + .......A1*A2*...An 的数根。

分析：有个对9取余的定理是可以直接求树根的，不过拿来玩大数运算也不错。ps.每位可以保存9位数，保存10位数会溢出。

高精度代码如下：

====================================================================================================================================

#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
using namespace std;

const int MAXN = 1007;
const long long Mod = 1e9;

struct BigNum
{
    int size;
    long long num[MAXN];

    BigNum(){
        size = 1;
        memset(num, false, sizeof(num));
    }
    void CarryBit()
    {
        for(int i=0; i<size; i++)
        {
            if(num[i] >= Mod)
            {
                num[i+1] += num[i] / Mod;
                num[i] %= Mod;

                if(i == size-1)
                    size += 1;
            }
        }
    }
    BigNum operator + (const BigNum &b)const
    {
        BigNum result;
        result.size = max(size, b.size);

        for(int i=0; i<result.size; i++)
            result.num[i] = num[i] + b.num[i];
        result.CarryBit();

        return result;
    }
    BigNum operator *(const long long &x)const
    {
        BigNum result;

        result.size = size;

        for(int i=0; i<size; i++)
            result.num[i] = num[i] * x;
        result.CarryBit();

        return result;
    }
};

int BitSum(long long x)
{
    int ans=0;

    while(x)
    {
        ans += x % 10;
        x /= 10;
    }

    return ans;
}

int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        long long N, x;
        BigNum sum, a;
        a.num[0] = 1;

        scanf("%lld", &N);

        while(N--)
        {
            scanf("%lld", &x);
            a = a * x;
            sum = sum + a;
        }

        int ans = 0;

        for(int i=0; i<sum.size; i++)
            ans += BitSum(sum.num[i]);

        while(ans >= 10)
            ans = BitSum(ans);

        printf("%d
", ans);
    }

    return 0;
}

对9取余代码如下：

=======================================================================================================================

#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
using namespace std;

int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        long long N, x, sum=1, ans=0;

        scanf("%lld", &N);

        while(N--)
        {
            scanf("%lld", &x);
            sum = (sum * x) % 9;
            ans += sum;
        }

        printf("%lld
", ans%9 ? ans%9:9);
    }

    return 0;
}