- it
- 洛谷 P5170 【模板】类欧几里得算法（三类经典类欧式子模板）
#include<iostream>
#include<stdio.h>
using namespace std
;
const int maxn
= 1e6 + 10;
typedef long long ll
;
const long long mod
= 998244353;
const long long inv2
= 499122177;
const long long inv6
= 166374059;
ll t
,n
,a
,b
,c
;
struct node
{
ll f
,g
,h
;
};
node
solve(long long a
, long long b
, long long c
, long long n
) {
node ans
, tmp
;
if(a
== 0)
{
ans
.f
= (b
/ c
) * (n
+ 1) % mod
;
ans
.g
= (b
/ c
) * n
% mod
* (n
+ 1) % mod
* inv2
% mod
;
ans
.h
= (b
/ c
) * (b
/ c
) % mod
* (n
+ 1) % mod
;
}
else if(a
>= c
|| b
>= c
)
{
tmp
= solve(a
% c
, b
% c
, c
, n
);
ans
.f
= (tmp
.f
+ n
* (n
+ 1) % mod
* inv2
% mod
* (a
/ c
) % mod
+ (n
+ 1) * (b
/ c
) % mod
) % mod
;
ans
.g
= (tmp
.g
+ (a
/ c
) * n
% mod
* (n
+ 1) % mod
* (2 * n
+ 1) % mod
* inv6
% mod
+ (b
/ c
) * n
% mod
* (n
+ 1) % mod
* inv2
% mod
) % mod
;
ans
.h
= (tmp
.h
+ (a
/ c
) * (a
/ c
) % mod
* n
% mod
* (n
+ 1) % mod
* (2 * n
+ 1) % mod
* inv6
% mod
+
(n
+ 1) * (b
/ c
) % mod
* (b
/ c
) % mod
+ 2 * (a
/ c
) % mod
* tmp
.g
% mod
+ 2 * (b
/ c
) % mod
* tmp
.f
% mod
+
2 * (a
/ c
) % mod
* (b
/ c
) % mod
* n
% mod
* (n
+ 1) % mod
* inv2
% mod
) % mod
;
}
else
{
long long m
= (a
* n
+ b
) / c
;
tmp
= solve(c
, c
- b
- 1, a
, m
- 1);
ans
.f
= (n
* (m
% mod
) % mod
- tmp
.f
) % mod
;
ans
.g
= (n
* (n
+ 1) % mod
* (m
% mod
) % mod
- tmp
.f
- tmp
.h
) % mod
* inv2
% mod
;
ans
.h
= (n
* (m
% mod
) % mod
* ((m
+ 1) % mod
) % mod
- 2 * tmp
.g
- 2 * tmp
.f
- ans
.f
) % mod
;
}
return ans
;
}
int main() {
scanf("%lld",&t
);
while(t
--) {
scanf("%lld%lld%lld%lld",&n
,&a
,&b
,&c
);
node ans
= solve(a
,b
,c
,n
);
printf("%lld %lld %lld\n",(ans
.f
+ mod
) % mod
,(ans
.h
+ mod
) % mod
,(ans
.g
+ mod
) % mod
);
}
return 0;
}
