类欧几里得算法
题目大意
求
$$ \begin{aligned} g(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor\\\\ h(a,b,c,n)=\sum_{i=0}^{n}i\lfloor\frac{ai+b}{c}\rfloor\\\\ h(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2 \end{aligned} $$
前置技能
- $$ a\leq \lfloor\frac cb\rfloor \Leftrightarrow ab\leq c $$
证明:
左边到右边:
$$
令 \ c=kb+r\\
a\leq\lfloor\frac cb\rfloor\Rightarrow a\leq k+r\Rightarrow ab\leq c-r\leq c
$$
右边到左边:
$$
ab\leq c\Rightarrow a\leq\frac cb=\lfloor\frac cb\rfloor+\frac rb \Rightarrow a\leq\lfloor\frac cb\rfloor
$$
推论
$$
a<\lfloor\frac cb\rfloor\Leftrightarrow ab+b\leq c
$$
- $$ n^2=2\sum_0^ni-n $$
类欧几里得算法
类欧几里得用来在 $O(logn)$内计算如下式
$$ f(a,b,c,n)=\sum_0^n{\lfloor\frac{ai+b}{c}\rfloor}\\\\ g(a,b,c,n)=\sum_0^n{i\lfloor\frac{ai+b}{c}\rfloor}\\\\ h(a,b,c,n)=\sum_0^n{\lfloor\frac{ai+b}{c}\rfloor}^2 $$
推倒 $f$式子
若a>=c||b>=c
$$ \begin{aligned} f(a,b,c,n)&=\sum_0^n\lfloor\frac{ai+b}{c}\rfloor\\\\ &=\sum_0^n\lfloor\frac{(\lfloor\frac ac\rfloor c+a\%c)i+(\lfloor\frac bc\rfloor c+b\%c)}{c}\rfloor\\\\ &=\lfloor\frac ac\rfloor\frac{n(n+1)}2+\lfloor\frac bc\rfloor n+f(a\%c,b\%c,c,n) \end{aligned} $$
若 a<c&&b<c
$$
\begin{aligned}
f(a,b,c,n)&=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor\\\\
&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}1\ \ \ 令\ m=\lfloor\frac{an+b}{c}\rfloor,\\\\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[j<\lfloor\frac{ai+b}{c}\rfloor]\\\\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[jc+c-b-1<ai]\\\\
&=\sum_{j=0}^{m-1}\sum_{i=0}^n[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]\\\\
&=nm-f(c,c-b-1,a,m-1)
\end{aligned}
$$
推倒 $g$式子
若a>=c||b>=c
$$
\begin{aligned}
g(a,b,c,n)&=\sum_{i=0}^n{i^2\lfloor\frac ac\rfloor+i\lfloor\frac ab\rfloor+g(a\%c,b\%c,c,n)}\\\\
&=\frac{n(n+1)(2n+1)}6\lfloor\frac ac\rfloor+\frac{n(n+1)}{2}\lfloor\frac ab\rfloor+g(a\%c,b\%c,c,n)
\end{aligned}
$$
若 a<c&&b<c
$$
\begin{aligned}
g(a,b,c,n)&=\sum_{j=0}^{m-1}i\sum_{i=0}^n[j<\lfloor\frac{ai+b}{c}\rfloor]\ \ \ 其中m=\lfloor\frac{an+b}{c}\rfloor\\\\
&=\sum_{j=0}^{m-1}i\sum_{i=0}^n[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]\\\\
&=\sum_{j=0}^{m-1}\frac{(n+t+1)(n-t)}{2}\ \ \ 其中t=\lfloor\frac{cj+c-b-1}{a}\rfloor\\\\
&=\frac 12(\sum_{j=0}^{m-1}{n(n+1)-(n+1)t-t^2})\\\\
&=\frac 12(mn(n+1)-(n+1)f(c,c-b-1,a,m-1)-h(c,c-b-1,a,m-1))
\end{aligned}
$$
推倒 $h$式子
若a>=c||b>=c
$$
\begin{aligned}
h(a,b,c,n)&=\sum_{i=0}^n{(i\lfloor\frac ac\rfloor+\lfloor\frac bc\rfloor+\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor)(i\lfloor\frac ac\rfloor+\lfloor\frac bc\rfloor+\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor)}\\\\
&=\sum_{i=0}^n((i\lfloor\frac ac\rfloor)^2+(\lfloor\frac bc\rfloor)^2+2\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor\lfloor\frac ac\rfloor i+2\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor\lfloor\frac bc\rfloor\\&+\lfloor\frac{(a\%c)i+(b\%c)}{c}\rfloor^2+2i\lfloor\frac bc\rfloor\lfloor\frac ac\rfloor)\\\\
&=\lfloor\frac ac\rfloor^2\frac{n(n+1)}{2}+n\lfloor\frac bc\rfloor+2\lfloor\frac bc\rfloor\lfloor\frac ac\rfloor\frac{n(n+1)}2\\\\
&+2\lfloor\frac bc\rfloor f((a\%c),(b\%c),c,n)+2\lfloor\frac ac\rfloor g((a\%c),(b\%c),c,n)+h((a\%c),(b\%c),c,n)
\end{aligned}
$$
若 a<c&&b<c
$$
\begin{aligned}
h(a,b,c,n)&=\sum_{i=0}^{n}{\lfloor\frac{ai+b}c\rfloor}^2\\\\
&=\sum_{i=0}^{n}(2\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}j-\lfloor\frac{ai+b}{c}\rfloor)\\\\
&=2\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1}(j+1)-f(a,b,c,n)\\\\
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^{n}[j<\lfloor\frac{ai+b}{c}\rfloor]-f(a,b,c,n)\\\\
&=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^{n}[i>\lfloor\frac{cj+c-b-1}{a}\rfloor]-f(a,b,c,n)\\\\
&=2\sum_{j=0}^{m-1}(j+1)(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)-f(a,b,c,n)\\\\
&=nm(m+1)-2\sum_{j=0}^{m-1}{j\lfloor\frac{cj+c-b-1}{a}\rfloor}-\sum_{j=0}^{m-1}{\lfloor\frac{cj+c-b-1}{a}\rfloor}-f(a,b,c,n)\\\\
&=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)
\end{aligned}
$$
计算
可以发现 $f,g,h$都只会用到已经算过的值,所以可以三个一起计算
蒟蒻丑陋的代码
// CREATED BY MASHIROYUKI
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, x, n) for(int i = x; i <= n; i ++ )
#define downrep(i, x, n) for(int i = n; i >= x; i -- )
template<typename T> void debug(T x) {cout << "#debug: " << x << endl;}
template<typename T> void debug(T x, T y) {cout << "#debug: " << x << " " << y << endl;}
template<typename T>
void read(T &x){
x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
}
typedef long long ll;
const ll mod=998244353,inv2=499122177,inv6=166374059;
ll C2(ll n) {
return (n*(n+1)>>1)%mod;
}
ll C3(ll n) {
return (n*(n+1)%mod*(2*n+1)%mod*inv6%mod)%mod;
}
struct Data {
ll f,g,h;
Data(ll _f=0,ll _g=0,ll _h=0):f(_f),g(_g),h(_h) {}
};
void add(ll &x,ll v) {
x+=(v%mod);
if(x>=mod) x-=mod;
}
Data Euclid(ll a,ll b,ll c,ll n) {
if(!a&&b<c) return Data();
if(a>=c||b>=c) {
Data now=Euclid(a%c,b%c,c,n);
ll _a=a/c,_b=b/c;
n%=mod;
add(now.h,_a*_a%mod*C3(n)%mod+_b*_b%mod*(n+1)%mod+_a*_b%mod*n%mod*(n+1)%mod+2*_a*now.g%mod+2*_b*now.f%mod);
add(now.f,_a*C2(n)%mod+_b*(n+1)%mod);
add(now.g,_a*C3(n)%mod+_b*C2(n)%mod);
return now;
}
ll m=(a*n+b)/c;
Data now,next=Euclid(c,c-b-1,a,m-1);
n%=mod,m%=mod;
now.f=((m*n%mod-next.f)%mod+mod)%mod;
now.g=((m*n%mod*(n+1)%mod-next.h-next.f)%mod+mod)%mod*inv2%mod;
now.h=((n*m%mod*(m+1)%mod-2*next.g-2*next.f-now.f)%mod+mod)%mod;
return now;
}
void solve()
{
ll n,a,b,c;
read(n),read(a),read(b),read(c);
Data ans=Euclid(a,b,c,n);
printf("%lld %lld %lld\n",ans.f,ans.h,ans.g);
}
signed main()
{
//IO
int _;
read(_);
while(_--) solve();
return 0;
}