是照着这个学的,不知道怎么炸了,有没有大佬来看看是哪里写错了啊,谢谢各位。
//
// 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;
}