P5170

发表于 更新于 分类于
【模板】类欧几里得算法

实际上这个名字很钓鱼啊。

试以 $O(\log n)$ 计算：
$$f( a , b ,c ,n ) = \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { a i + b } { c } \right \rfloor$$

尝试简化问题：

$$
\begin{aligned}
f ( a , b , c , n ) = & \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { a i + b } { c } \right \rfloor
\\
= & \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { (\lfloor a / c \rfloor c + a \bmod c) i + ( \lfloor b / c \rfloor c + b \bmod c ) } { c } \right \rfloor
\\
= & \dfrac { n ( n + 1 )} { 2 } \left\lfloor \dfrac { a } { c } \right\rfloor + ( n + 1 ) \left\lfloor \dfrac { b } { c } \right\rfloor + \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { ( a \bmod c ) i + ( b \bmod c)} { c } \right \rfloor
\\
= & \dfrac { n ( n + 1 )} { 2 } \left\lfloor \dfrac { a } { c } \right\rfloor + ( n + 1 ) \left\lfloor \dfrac { b } { c } \right\rfloor + f ( a \bmod c , b \bmod c , c , n)
\end{aligned}
$$

这样问题就只要解决 $a , b < c$ 情况的快速求和了。

尝试变换和式：

$$
\begin{aligned}
f( a, b ,c , n) = & \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { a i + b } { c } \right \rfloor
\\
= & \sum _ { i = 0 } ^ { n } \sum _ { j = 0 } ^ { \lfloor ( a i + b ) / c \rfloor - 1 } 1
\\
= & \sum _ { j = 0 } ^ { \lfloor ( a n + b ) / c \rfloor - 1 } \sum _ { i = 0 } ^ { n } \left[ j < \left \lfloor \dfrac { a i + b } { c } \right \rfloor \right]
\end{aligned}
$$

考虑变换艾弗森括号内的命题。

$$
j < \left \lfloor \dfrac { a i + b } { c } \right \rfloor
$$

该命题等价于：

$$
j + 1 \le \left \lfloor \dfrac { a i + b } { c } \right \rfloor
$$

等价于：

$$
j + 1 \le \dfrac { a i + b } { c }
$$

等价于：

$$
j c + c \le a i + b
$$

等价于：

$$
j c + c - b - 1 < a i
$$

等价于：

$$
i > \left \lfloor \dfrac {j c + c - b - 1 } { a } \right \rfloor
$$

现在考虑代进原式吧，令 $ m = \lfloor ( a n + b ) / c \rfloor$：

$$
\begin{aligned}
f ( a , b , c ,n) = & \sum _ { j = 0 } ^ { m - 1 } \sum _ { i = 0 } ^ { n } \left[ i > \left \lfloor \dfrac {j c + c - b - 1 } { a } \right \rfloor \right]
\\
= & \sum _ { j = 0 } ^ { m - 1 } \left ( n - \left \lfloor \dfrac {j c + c - b - 1 } { a } \right \rfloor \right )
\\
= & nm - f ( c , c - b - 1 , a , m - 1 )
\end{aligned}
$$

先取模再递归，非常像欧几里得算法，也容易发现该算法的复杂度是 $ O (\log n ) $ 的。

上面是最简单的一个问题。

下面是两个变种：

$$ g ( a , b ,c , n) = \sum _ { i = 0 } ^ { n } i \left \lfloor \dfrac { a i + b } { c } \right \rfloor$$
$$ h ( a , b ,c , n) = \sum _ { i = 0 } ^ { n } \left \lfloor \dfrac { a i + b } { c } \right \rfloor ^ 2 $$

对于函数 $g$：

$$
\begin{aligned}
g ( a , b ,c ,n) = & g ( a \bmod c, b \bmod c , c ,n)
\\
& + \dfrac { n ( n + 1 ) ( 2 n + 1 ) } { 6 } \left\lfloor \dfrac{ a } { c } \right \rfloor + \dfrac { n ( n + 1 ) } { 2 } \left \lfloor \dfrac { b } { c } \right \rfloor
\end{aligned}
$$

只需要考虑 $a, b < c$ 的情况。令 $ m = \lfloor ( a n + b ) / c \rfloor$：

$$
\begin{aligned}
g ( a, b , c ,n ) = & \sum _ { i = 0 } ^ { n } i \left \lfloor \dfrac { a i + b } { c } \right \rfloor
\\
= & \sum _ { j = 0 } ^ { m - 1 } \sum _ { i = 0 } ^ { n } \left[ j < \left \lfloor \dfrac { a i + b } { c } \right \rfloor \right] i
\end{aligned}
$$

设 $t = \lfloor ( j c + c - b - 1 ) / a \rfloor$，我们能得到：

$$
\begin{aligned}
g ( a , b , c , n ) = & \sum _ { j = 0 } ^ { m - 1 } \sum _ { i = 0 } ^ { n } [ i > t ] i
\\
= & \sum _ { j = 0 } ^ { m - 1 } \dfrac { ( t + n + 1 ) ( n - t ) } { 2 }
\\
= & \dfrac { 1 } { 2 } \left ( m n ( n + 1 ) - \sum _ { j = 0 } ^ { m - 1 } t ^ 2 - \sum _ { j = 0 }^ { m - 1 } t \right )
\\
= & \dfrac { 1 } { 2 } \left ( m n ( n + 1 ) - h ( c , c - b - 1 , a , m - 1 ) - f ( c , c - b -1 , a , m - 1 ) \right )
\end{aligned}
$$

对于函数 $h$：

$$
\begin{aligned}
h (a ,b , c ,n) = & h ( a \bmod c, b \bmod c, c ,n)
\\
& + 2 \left \lfloor \dfrac{ b } { c } \right \rfloor f( a \bmod c, b \bmod c, c ,n) + 2 \left \lfloor \dfrac{ a } { c } \right \rfloor g( a \bmod c, b \bmod c, c ,n)
\\
& + \left \lfloor \dfrac { a } { c } \right \rfloor ^ 2 \dfrac { n ( n + 1 ) ( 2 n + 1 ) } { 6 } + \left \lfloor \dfrac { b } { c } \right \rfloor ^ 2 ( n + 1 ) + \left \lfloor \dfrac { a } { c } \right \rfloor \left \lfloor \dfrac { b } { c } \right \rfloor n ( n + 1 )
\end{aligned}
$$

现在也只需要考虑 $a , b < c$ 的情况了。

同样，我们设 $ m = \lfloor ( a n + b ) / c \rfloor$，$ t = \lfloor ( j c + c - b - 1 ) / a \rfloor$。

然后我们换一种平方的处理方式：

$$
n ^ 2 = 2 \dfrac { n ( n + 1 ) } { 2 } - n = \left( 2 \sum _ { i = 1 } ^ { n } i \right) - n
$$

于是就有：

$$
\begin{aligned}
h ( a, b, c, n ) = & \sum _ { i = 0 } ^ { n } \left\lfloor \dfrac {a i + b } { c } \right\rfloor ^ 2
\\
= & \sum _ { i = 0 } ^ { n } \left[ \left ( 2 \sum _ { j = 1 } ^ { \lfloor ( a i + b ) / c \rfloor} j\right ) - \left \lfloor \dfrac { a i + b } { c } \right \rfloor\right]
\\
= & \left( 2 \sum _ { i = 0 } ^ { n } \sum _ { j = 1 } ^ { \lfloor ( a i + b) / c \rfloor} j\right) - f ( a , b , c , n )
\\
= & \left( 2 \sum _ { i = 0 } ^ { n } \sum _ { j = 0 } ^ { \lfloor ( a i + b) / c \rfloor - 1 } ( j + 1 )\right) - f ( a , b , c , n )
\\
= & \left( 2 \sum _ { j = 0 } ^ { m - 1 } ( j + 1 ) \sum _ { i = 0 } ^ { n } \left[ j < \left \lfloor \dfrac {a i + b} { c } \right\rfloor \right] \right) - f ( a , b , c , n )
\\
= & \left( 2 \sum _ { j = 0 } ^ { m - 1 } ( j + 1 ) \sum _ { i = 0 } ^ { n } \left[ i > t \right] \right) - f ( a , b , c , n )
\\
= & \left( 2 \sum _ { j = 0 } ^ { m - 1 } ( j + 1 ) ( n - t ) \right) - f ( a , b , c , n )
\\
= & \left ( n m ( m +1 ) - 2 \sum _ { j = 0 } ^ { m - 1 } ( j + 1 ) \left\lfloor \dfrac {j c + c - b - 1 } { a } \right\rfloor \right ) - f( a ,b, c , n)
\\
= & n m ( m +1 ) - 2 g ( c, c - b - 1 ,a ,m -1 )
\\
& - 2 f ( c, c - b - 1 , a , m - 1 ) - f( a ,b, c , n)
\end{aligned}
$$

具体实现的时候采用整体递归。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}

const ll mo=998244353;

inline ll Pow(ll b,ll p) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

ll T,inv2,inv6;

struct node{inline node(ll x=0,ll y=0,ll z=0) {f=x;g=y;h=z;};ll f,g,h;};

inline node Solve(ll a,ll b,ll c,ll n) {
  ll s1=(n*(n+1)%mo)*inv2%mo,s2=(n*(n+1)%mo)*((2*n+1)*inv6%mo)%mo;
  if(a==0) {
    node res;
    res.f=(b/c)*(n+1)%mo;
    res.g=(b/c)*s1%mo;
    res.h=((b/c)*(b/c)%mo)*(n+1)%mo;
    return res;
  }
  node res;
  if(a<c&&b<c) {
    ll m=(a*n+b)/c;node tmp=Solve(c,c-b-1,a,m-1);
    res.f=(n*m%mo-tmp.f+mo)%mo;
    res.g=(m*n%mo)*(n+1)%mo;res.g=(res.g-tmp.h+mo)%mo;
    res.g=(res.g-tmp.f+mo)%mo;res.g=res.g*inv2%mo;
    res.h=(n*m%mo)*(m+1)%mo;
    res.h=(res.h-tmp.g-tmp.g+mo+mo)%mo;
    res.h=(res.h-tmp.f-tmp.f+mo+mo)%mo;
    res.h=(res.h-res.f+mo)%mo;
  }
  else {
    node tmp=Solve(a%c,b%c,c,n);
    res.f=s1*(a/c)%mo;
    res.f=(res.f+(n+1)*(b/c)%mo)%mo;res.f=(res.f+tmp.f)%mo;
    res.g=(s2*(a/c))%mo;
    res.g=(res.g+(s1*(b/c))%mo)%mo;
    res.g=(res.g+tmp.g)%mo;
    res.h=tmp.h;
    res.h=(res.h+2*(b/c)*tmp.f%mo)%mo;
    res.h=(res.h+2*(a/c)*tmp.g%mo)%mo;
    res.h=(res.h+((a/c)*(a/c)%mo)*s2%mo)%mo;
    res.h=(res.h+((b/c)*(b/c)%mo)*(n+1)%mo)%mo;
    res.h=(res.h+((a/c)*(b/c)%mo)*(n*(n+1)%mo)%mo)%mo;
  }
  return res;
}

inline void Init() {
  inv2=Pow(2,mo-2);inv6=Pow(6,mo-2);
}

int main() {

  T=read();Init();

  while(T--) {
    ll n,a,b,c;
    n=read();a=read();b=read();c=read();
    node tmp=Solve(a,b,c,n);
    writes(tmp.f);writes(tmp.h);writeln(tmp.g);
  }

  return 0;
}