学习心得 - 类欧
ExFish
·
·
算法·理论
今天做到了 ABC402 G，学习一下哈。
【SX/NOI-】类欧
类欧的名字是因为这个算法类似于辗转相除，其实就是复杂度计算而已。
其他没什么关系了。
这个算法主要是求在一条直线下的整点有多少个。
按照例题，它当然可以用来求：
f(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor \\
g(a,b,c,n)= \sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor^2 \\
h(a,b,c,n)=\sum_{i=0}^ni\lfloor \frac{ai+b}{c}\rfloor
算法推理 f 函数
我们注意到 a\ge c 或 b\ge c 时显然可以直接除掉多余部分。
可以变为
\begin{aligned}
f(a,b,c,n)
&=\sum_{i=0}^n\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor+i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c} \rfloor \\
&=f(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor \frac{b}{c} \rfloor
\end{aligned}
否则，考虑提出。
f(a,b,c,n)=\sum_{i=0}^n\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[j\leq\lfloor \frac{ai+b}{c}\rfloor]
考虑整理第二层。
\begin{aligned}
\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[j\leq\lfloor \frac{ai+b}{c}\rfloor]&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}[jc+c<{ai+b}+1]\\
&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}[jc+c-b-1<ai]\\
\end{aligned}
我们知道 \sum 是可以调换的。
考虑调换。
\begin{aligned}
f(a,b,c,n)
&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[jc+c-b-1<ai]\\
&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}\sum_{i=0}^n[i>\lfloor\frac{jc+c-b-1}{a}\rfloor]\\
&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}n-\lfloor\frac{jc+c-b-1}{a}\rfloor\\
&=n{\lfloor \frac{an+b}{c}\rfloor}-f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)
\end{aligned}
ok 在你头晕之前我们总结出一个类似辗转相除的式子。
这里少了个 a=0 应该直接带入就看得懂吧。
f(a,b,c,n)=
\begin{cases}
(n+1)\lfloor{\frac{b}{c}}\rfloor & a=0 \\
f(a\bmod c,b\mod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor \frac{b}{c} \rfloor & a\ge c\vee b\ge c \\
n{\lfloor \frac{an+b}{c}\rfloor}-f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1) & otherwise
\end{cases}
这就是我们最后归纳的式子。
算法推理 g,h 函数
同理，a=0。
g(a,b,c,n)=(n+1)\lfloor\frac{b}{c}\rfloor^2 \\
h(a,b,c,n)=\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor
然后是 a\ge c \vee b\ge c。
这个贼乱，分开来打。
先看 g。
\begin{aligned}
g(a,b,c,n)
&=\sum_{i=0}^n(\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor+i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c} \rfloor)^2 \\
&=\sum_{i=0}^n(\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor)^2+2(\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor)(i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c}\rfloor)+({i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c}} \rfloor)^2 \\
&=\sum_{i=0}^n(\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor)^2+2\sum_{i=0}^n(\lfloor\frac{i(a\bmod c)+(b\bmod c)}{c}\rfloor)(i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c}\rfloor)+\sum_{i=0}^n({i\lfloor\frac{a}{c}\rfloor+\lfloor \frac{b}{c}} \rfloor)^2 \\
&=g(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{a}{c} \rfloor h(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{b}{c} \rfloor f(a \bmod c,b \bmod c,c,n)+\sum_{i=0}^n(\lfloor i\frac{a}{c}\rfloor)^2+2i\lfloor\frac{a}{c}\rfloor \lfloor\frac{b}{c}\rfloor+\lfloor\frac{b}{c}\rfloor^2 \\
&=g(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{a}{c} \rfloor h(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{b}{c} \rfloor f(a \bmod c,b \bmod c,c,n)+\frac{n(n+1)(2n+1)}{6}{\lfloor \frac{a}{c}\rfloor}^2+n(n+1)\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor^2
\end{aligned}
神经中枢爆炸......
看 h，看起来简单多了 /ll。
\begin{aligned}
h(a,b,c,n)
&=\sum_{i=0}^n i\lfloor \frac{i(a\bmod c)+b\bmod c}{c} \rfloor+i(i\lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c}\rfloor)\\
&=h(a\bmod c,b\bmod c,c,n)+\sum_{i=0}^n i^2\lfloor \frac{a}{c} \rfloor+i\lfloor \frac{b}{c}\rfloor\\
&=h(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor \frac{a}{c} \rfloor+\frac{n(n+1)}{2}\lfloor \frac{b}{c} \rfloor
\end{aligned}
接下来是分析其他情况。
先来 g。
\begin{aligned}
g(a,b,c,n)
&=2\sum_{i=0}^n\sum_{j=1}^{\lfloor \frac{ai+b}{c}\rfloor}j-\sum_{i=0}^n{\lfloor \frac{ai+b}{c}\rfloor}\\
&=(2\sum_{i=0}^n\sum_{j=1}^{{\lfloor \frac{an+b}{c}\rfloor}}j[j\leq {\lfloor \frac{ai+b}{c}\rfloor}])-f(a,b,c,n)\\
&=(2\sum_{i=0}^n\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor}-1}(j+1)[jc+c-1<ai+b])-f(a,b,c,n)\\
&=(2\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor}-1}(j+1)\sum_{i=0}^n[jc+c-1<ai+b])-f(a,b,c,n)\\
&=(2\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor}-1}(j+1)\sum_{i=0}^n[i>\lfloor\frac{jc+c+b-1}{a}\rfloor])-f(a,b,c,n)\\
&=(2\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor}-1}(j+1)(n-\lfloor\frac{jc+c+b-1}{a}\rfloor))-f(a,b,c,n)\\
&=n{\lfloor \frac{an+b}{c}\rfloor}({\lfloor \frac{an+b}{c}\rfloor}+1)-f(a,b,c,n)-2h(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)-2f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)\\
\end{aligned}
脑子炸掉的同学可以先做模板题的前两问。
相对简单的是 h。
\begin{aligned}
h(a,b,c,n)
&=\sum_{i=0}^n i \sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[j\leq {\lfloor \frac{ai+b}{c}\rfloor}]\\
&=\sum_{i=0}^n i \sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}[jc+c-1<ai+b]\\
&=\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}\sum_{i=0}^n i[i>\lfloor \frac{jc+c-b-1}{a} \rfloor]\\
&=\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor-1}}\frac{n(n+1)}{2}-\sum_{i=0}^{\lfloor \frac{jc+c-b-1}{a} \rfloor}i\\
&=\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor-1}}\frac{n(n+1)}{2}-\frac{{\lfloor \frac{jc+c-b-1}{a} \rfloor}({\lfloor \frac{jc+c-b-1}{a} \rfloor}+1)}{2}\\
&=\sum_{j=0}^{{\lfloor \frac{an+b}{c}\rfloor-1}}\frac{n(n+1)}{2}-\frac{{\lfloor \frac{jc+c-b-1}{a} \rfloor}({\lfloor \frac{jc+c-b-1}{a} \rfloor}+1)}{2}\\
&=\frac{{\lfloor \frac{an+b}{c}\rfloor}n(n+1)-g(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)-f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)}{2}
\end{aligned}
我们总结一下哈：
g(a,b,c,n)=
\begin{cases}
(n+1)\lfloor{\frac{b}{c}}\rfloor^2 & a=0 \\
g(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{a}{c} \rfloor h(a \bmod c,b \bmod c,c,n)+2\lfloor \frac{b}{c} \rfloor f(a \bmod c,b \bmod c,c,n)+\frac{n(n+1)(2n+1)}{6}{\lfloor \frac{a}{c}\rfloor}^2+n(n+1)\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor^2 & a\ge c\vee b\ge c \\
n{\lfloor \frac{an+b}{c}\rfloor}({\lfloor \frac{an+b}{c}\rfloor}+1)-f(a,b,c,n)-2h(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)-2f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1) & otherwise
\end{cases}
h(a,b,c,n)=
\begin{cases}
\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor & a=0 \\
h(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor \frac{a}{c} \rfloor+\frac{n(n+1)}{2}\lfloor \frac{b}{c} \rfloor & a\ge c\vee b\ge c \\
\frac{{\lfloor \frac{an+b}{c}\rfloor}n(n+1)-g(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)-f(c,c-b-1,a,{\lfloor \frac{an+b}{c}\rfloor}-1)}{2}& otherwise
\end{cases}
你肯定已经崩溃了 qwq。
那你还看模板题代码吗
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct func{
ll f,g,h;
}res;
const ll p=998244353,p2=499122177,p6=166374059;
func solve(ll n,ll a,ll b,ll c){
func ans,nxt;
if(a==0){
ans.f=(b/c)*(n+1)%p;
ans.g=(b/c)*(b/c)%p*(n+1)%p;
ans.h=(b/c)*n%p*(n+1)%p*p2%p;
}else if(a>=c||b>=c){
nxt=solve(n,a%c,b%c,c);
ans.f=(nxt.f+n*(n+1)%p*p2%p*(a/c)%p+(n+1)*(b/c)%p)%p;
ans.g=(nxt.g+(a/c)*(a/c)%p*n%p*(n+1)%p*(2*n+1)%p*p6%p+(n+1)*(b/c)%p*(b/c)%p+2*(a/c)%p*nxt.h%p+2*(b/c)%p*nxt.f%p+2*(a/c)%p*(b/c)%p*n%p*(n+1)%p*p2%p)%p;
ans.h=((a/c)*n%p*(n+1)%p*(2*n+1)%p*p6%p+(b/c)*n%p*(n+1)%p*p2%p+nxt.h)%p;
}else{
ll m=(a*n+b)/c,pm=m%p;
nxt=solve(m-1,c,c-b-1,a);
ans.f=(n*pm%p-nxt.f)%p;
ans.g=(n*pm%p*((m+1)%p)%p-2*nxt.h-2*nxt.f-ans.f+p)%p;
ans.h=(n*(n+1)%p*pm%p-nxt.f-nxt.g)%p*p2%p;
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
ll n,a,b,c;
cin>>n>>a>>b>>c;
res=solve(n,a,b,c);
cout<<(res.f+p)%p<<" "<<(res.g+p)%p<<" "<<(res.h+p)%p<<"\n";
}
return 0;
}
【NOI/NOI+/CTSC】ABC402G
在上面 7500+ 字之后，我们进入正题（
本质求
\frac{a^2n(n+1)(2n+1)}{6}+\frac{a(b_1+b_2)n(n+1)}{2}+(n+1)b_1b_2+\frac{c^2(g(n,a,b_1,c)+g(n,a,b_2,c)-f(n,a,b_1,c)+f(n,a,b_2,c))}{2}-c[a(h(n,a,b_1,c)+h(n,a,b_2,c))+b_1f(n,a,b_2,c)+b_2f(n,a,b_1,c)]
推式子的部分以后再补充。
【NOI/NOI+/CTSC】ABC283Ex
upd 2025/05/17.
人生中第一道 Ex 题！
本质求
\sum_{i=0}^{30 } f(\lfloor \frac{n-r}{m}\rfloor，m,r,2^i)-2f(\lfloor \frac{n-r}{m}\rfloor，m,r,2^{i+1})
为什么呢？看原式。
\begin{aligned}
\sum_{i\bmod m=r}^n \operatorname{pc}(i)
&=\sum_{i\bmod m=r}^n \sum_{j=0}^{30} [\lfloor \frac{i}{2^j}\rfloor\bmod 2=1] \\
&=\sum_{j=0}^{30}\sum_{i\bmod m=0}^{n-r} [\lfloor \frac{i+r}{2^j}\rfloor\bmod 2=1] \\
&=\sum_{j=0}^{30}\sum_{i=0}^{\lfloor \frac{n-r}{m}\rfloor} [\lfloor\frac{im+r}{2^j}\rfloor\bmod 2=1] \\
&=\sum_{j=0}^{30}\sum_{i=0}^{\lfloor \frac{n-r}{m}\rfloor} [\lfloor\frac{im+r}{2^j}\rfloor-2\times \lfloor \frac{\lfloor\frac{im+r}{2^j}\rfloor}{2}\rfloor=1] \\
&= \sum_{j=0}^{30}\sum_{i=0}^{\lfloor \frac{n-r}{m}\rfloor} \lfloor\frac{im+r}{2^j}\rfloor-2\times \lfloor {\frac{im+r}{2^{j+1}}}\rfloor
\end{aligned}
对比原来的 f 函数：
f(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor
显然直接转化。
【SX/NOI-】P5171
upd 2025/05/21.
求的是 ax+by\leq c 的非负整数解。
学过初中数学的就可以知道：
\begin{aligned}
ax+by & \leq c \\
by & \leq c-ax\\
y & \leq \frac{c-ax}{b}
\end{aligned}
由于是非负整数解，所以：
y\leq\lfloor \frac{c-ax}{b} \rfloor
那么对于 y 有 \lfloor \frac{c-ax}{b} \rfloor+1 个非负整数解。
考虑枚举 x，注意：
\begin{aligned}
c-ax&\ge 0\\
ax&\le c\\
x&\le \frac{c}{a}
\end{aligned}
我们可以确定枚举上界为 \lfloor \frac{c}{a} \rfloor。
答案就是
\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c-ax}{b} \rfloor+1
但这 x 的系数怎么是 -a？？
我们需要变形：
\begin{aligned}
\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c-ax}{b} \rfloor+1 &=\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c+(b-a)x}{b} \rfloor-x+1 \\
&=\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c+(b-a)x}{b} \rfloor-\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}x+\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}1 \\
&=\lfloor \frac{c}{a} \rfloor+ (\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c+(b-a)x}{b} \rfloor)-\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}x\\
&=\lfloor \frac{c}{a} \rfloor+ (\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c+(b-a)x}{b} \rfloor)-\frac{\lfloor \frac{c}{a} \rfloor(\lfloor \frac{c}{a} \rfloor+1)}{2}
\end{aligned}
你学会了吗？
【SX/NOI-】ABC408G & P5179
upd 2025/06/04.
类欧思想练手题。（纪第一次切 G）
考虑一个同样类似欧几里得的做法。（主要是思想，不是函数相同）
下文同步载于 G 题题解区。
是这么一个东西，原式满足不等式：
\frac{a}{b}<\frac{p}{q}<\frac{c}{d}
取倒数：
\frac{d}{c}<\frac{q}{p}<\frac{b}{a}
分离常数，设 v=\lfloor \frac{d}{c} \rfloor ：
\frac{d-cv}{c}<\frac{q-vp}{p}<\frac{b-va}{a}
其实就是：
\frac{d\bmod c}{c}<\frac{q-vp}{p}<\frac{b-va}{a}
递归，我们发现：
$$
\frac{a}{b}<1<\frac{c}{d}
$$
那么取 $p=1,q=1$。
本质就是递归到这个状态。
然后我们可以考虑逆推，每一次都有调换。
最后输出答案 $q$ 即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
void gcd(int a,int b,int &p,int &q,int c,int d){
if(a<b&&c>d)
p=1,q=1;
else{
gcd(d%c,c,q,p,b-(d/c)*a,a);
q+=(d/c)*p;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--){
int a,b,c,d;
cin>>a>>b>>c>>d;
int p,q;
gcd(a,b,p,q,c,d);
cout<<q<<"\n";
}
}
```
代码跟上面一样，我就不过多赘述了。
但是求答案有必要讲一下，为什么要加回来呢？
我们倒推时其实不知道 $p$，$q$ 的值，只有倒推回来时才知道上一步的值，所以要加回 $vp$，才是原本 $q$ 的值。
综上，此题难度是小学数学题。