POJ 3982 序列（高精度加法）

系统管理员 2022-06-09 02:08 213阅读 0赞

数列A满足An = An-1 + An-2 + An-3, n >= 3  
  
编写程序，给定A0, A1 和 A2, 计算A99

Input

输入包含多行数据  
  
每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)  
数据以EOF结束

Output

对于输入的每一行输出A99的值

Sample Input

1 1 1

Sample Output

69087442470169316923566147

思路：

直接高精度模拟就好了，直接套模板

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    class bigInt
    {
    public:
        int num[302], len;
        bigInt() { num[0] = 0, len = 0; }
        void operator=(const int &a)
        {
            int tmp = a;
            len = 0;
            while (tmp)
                num[len++] = tmp % 10, tmp /= 10;
            if (!len) num[0] = 0, len = 1;
        }
        bigInt(const int &a)
        {
            int tmp = a;
            len = 0;
            while (tmp)
                num[len++] = tmp % 10, tmp /= 10;
            if (!len) num[0] = 0, len = 1;
        }
        bigInt operator+(const bigInt &a)
        {
            bigInt res;
            int i, j, c = 0, adda, addb;
            for (i = 0, j = 0; i < len || j < a.len || c; )
            {
                adda = 0, addb = 0;
                if (i < len)
                    adda = num[i++];
                if (j < a.len)
                    addb = a.num[j++];
                res.num[res.len++] = (adda + addb + c) % 10;
                c = (adda + addb + c) / 10;
            }
            return res;
        }
        void display()
        {
            int i;
            for (i = len - 1; i > 1; i--)
                if (num[i]) break;
            for (; i >= 0; i--)
                printf("%d", num[i]);
            printf("\n");
        }
    };
    int main()
    {
        int a,b,c,i;
        while(scanf("%d%d%d",&a,&b,&c)!=EOF)
        {
            bigInt x,y,z,t;
            y=a;
            z=b;
            t=c;
            for(i=1;i<=97;i++)
            {
                x=y;
                y=z;
                z=t;
                t=x+y;
                t=t+z;
            }
            t.display();
        }
        return 0;
    }