蓝桥杯_入门系列_序列求和

分手后的思念是犯贱 2022-05-03 03:28 185阅读 0赞

高精度 求和公式S=n\*(n+1)/2

需要高精+低精 高精\*高精 高精/低精三个运算

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        char n1[100];
        int n[100], n_1[100], out[200], lenn, lenn_1, lenout;
        memset(n, 0, sizeof(n));
        memset(n_1, 0, sizeof(n_1));
        memset(out, 0, sizeof(out));
        cin >> n1;
        lenn = strlen(n1);
        lenn_1 = lenn;
        for (int i = 0; i < lenn; i++) {
            n[lenn - i-1] = n1[i] - '0';
            n_1[lenn - i - 1] = n[lenn - i - 1];
        }
        n_1[0] = n[0] + 1;
        int x = n_1[0] / 10,i=0;
        while (x != 0) {
            n_1[i] %= 10;
            n_1[i + 1]++;
            x = n_1[i+1] / 10;
            i++;
        }
        if (n_1[lenn_1] != 0)
            lenn_1++;
        /*
        //测试加法是否正确
        for (int i = 0; i < lenn; i++)
            cout << n[i];
        cout << endl;
        for (int i = 0; i < lenn_1; i++)
            cout << n_1[i];
        cout << endl;*/
    
        //高精度乘法
        for (int i = 0; i < lenn; i++) {
            x = 0;
            for (int j = 0; j < lenn_1; j++) {
                out[i + j] = out[i + j] + n[i] * n_1[j] + x;
                x = out[i + j] / 10;
                out[i + j] %= 10;
            }
            out[lenn_1 + i] = x;
        }
        lenout = lenn + lenn_1;
        while (out[lenout]==0&&lenout>0)//1 <= r <= 10000, out!=0恒成立
            lenout--;
        x = 0;
        int before;
        for (i = lenout ; i >= 0; i--) {
            before = out[i];
            out[i] = (x * 10 + out[i]) / 2;
            x = (x * 10 + before) %2;//余数
        }
        while (out[lenout] == 0 && lenout>0)
            lenout--;
        for (i = lenout; i >= 0; i--)
            cout << out[i];
        return 0;
    }