求助类欧几里得
查看原帖
求助类欧几里得
234011
Cat_shao楼主2022/8/1 22:50

是照着这个学的,不知道怎么炸了,有没有大佬来看看是哪里写错了啊,谢谢各位。

//
// Created by XH on 2022/8/1.
//

#include <bits/stdc++.h>

using namespace std;

namespace Main {
    const long long MOD = 998244353;

    class ll {
    public:
        long long x;
        ll(long long _x = 0) : x(_x % MOD) {}

        operator long long() {
            return x;
        }

        ll operator+(long long y) {
            return (x + y) % MOD;
        }

        ll operator-(long long y) {
            return (x - y) % MOD;
        }

        ll operator*(long long y) {
            return x * y % MOD;
        }
    };

    ll INV2 = 499122177, INV6 = 166374059;

    typedef tuple<ll, ll, ll> TII;

    TII likeGcd(long long a, long long b, long long c, long long n) {
        if (n == 0 || a == 0) {
            return {0, 0, 0};
        }
        ll p = c - b + a - 1, p1 = n, p2 = INV2 * n * (n - 1), p3 = INV6 * n * (n - 1) * (2 * n - 1);
        ll f, g, h;
        if (a >= c || b >= c) {
            ll ma = a / c, ra = a % c, mb = b / c, rb = b % c;
            tie(f, g, h) = likeGcd(ra, rb, c, n);
            return {
                p2 * ma + p1 * mb + f,
                p3 * ma + p2 * mb + g,
                p3 * ma * ma + p2 * ma * mb * 2ll + p1 * mb * mb +
                mb * f * 2ll + ma * g * 2ll + h
            };
        } else {
            ll m = (a * (n - 1) + b) / c, f2;
            tie(f, g, h) = likeGcd(c, p, a, m);
            return {
                f2 = m * n - f,
                (m * n * (n - 1ll) - h + f) * INV2,
                m * n * (m - 1ll) - g * 2ll + f2
            };
        }
    }

    void main() {
        long long T, a, b, c, n;
        ll f, g, h;
        cin >> T;
        while (T--) {
            cin >> n >> a >> b >> c;
            tie(f, g, h) = likeGcd(a, b, c, n + 1);
            f = f + MOD;
            g = g + MOD;
            h = h + MOD;
            cout << f << ' ' << g << ' ' << h << endl;
        }
    }
}

int main() {
    Main::main();
    return 0;
}
2022/8/1 22:50
加载中...