学习笔记 - 类欧几里得算法 | Lucky_Glass's Blog
0%

学习笔记 - 类欧几里得算法

#gan出博客评论过后开始正经写博客#


# 类欧几里得算法

欧几里得算法是计算 $(a,b)$,主要思想是 $(a,b)=(b\bmod a,a)$。这样保证了它的时间复杂度。

而类欧几里得算法,并不是像扩展欧几里得算法那样,它的正确性和欧几里得算法没有任何关系,只是它也有类似于 $(a,b)\to(b\bmod a,a)$ 这种操作,从而保证时间复杂度。

常见的 $3$ 种(然而我并不知道还有没有别的)可以用类欧几里得算法计算的式子有:


# 算法主体

- 计算 f

当然从看起来最简单的入手~

看到下取整,我们可以先把我们能够提取出的整数部分提取出来——当 $a\ge c$ 或 $b\ge c$ 时,令 $a’=a\bmod c$,$b’=b\bmod c$:

经过这一步后,有 $a<c$ 且 $b<c$。在此基础上继续:令 $m=\left\lfloor\frac{an+b}{c}\right\rfloor$

Warning!!! 公式恐惧者慎入

注意到上式的 $a,b$ 实际上是对 $c$ 取模得到的。因此,我们相当于完成了 $(a,c)\to(a\bmod c,c)\to(c,a\bmod c)$。根据欧几里得算法的证明,可以得到该算法在复杂度上的正确性。

> Addition

边界情况也就是 $a=0$,代入原式,可得 $f(0,b,c,n)=(n+1)\left\lfloor\frac bc\right\rfloor$。

- 计算 g

你会知道为什么要先讲 $f(a,b,c,n)$ 的……

和计算 f 一样的思路,先给 $a\bmod c$,$b\bmod c$:

> Addition

基本上每篇博客都说计算 $i^2$ 的前缀和是基本操作,然后不讲…… QwQ 然而我不会,太菜了

首先有 $(i+1)^3-i^3=3i^2+3i+1$,所以:

移项过后可得

然后就可以愉快的继续了~ 再考虑 $a<c$ 且 $b<c$ 的情况。仍然令 $m=\left\lfloor\frac{an+b}c\right\rfloor$,

可以看到这几个函数乱七八糟互相嵌套……但是复杂度还是正确的~

> Hint

别忘了 1/2!

- 计算 h

已经熟悉了的套路:

真是够麻烦的……

继续吧?然而发现因为有平方,不能按之前的方法把 $\left\lfloor\frac{ai+b}{c}\right\rfloor$ 拆成求和式,这时候就需要在 OI-wiki 上找一下骚操作了 awa:

为了公式好看一点,定义 $m_i=\left\lfloor\frac{ai+b}{c}\right\rfloor$。

这个式子意义何在?注意到 $\frac{m_i(m_i+1)}2$ 是 $1,…,m_i$ 的和。那么:

想办法处理前面的求和式:

> Hint

# 处的推导,可以考虑有多少个 $i$ 能够取到 $(j+1)$

怎么又套了另外的函数……看来这几个函数一起求 (!见代码)是被安排好了的


# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD=998244353,inv2=499122177,inv6=166374059;

#define sum1(n) (n*(n+1ll)%MOD*inv2%MOD)
#define sum2(n) (n*(n+1ll)%MOD*(2ll*n+1)%MOD*inv6%MOD)

struct DATA{
ll f,g,h;
};

DATA Calc(ll n,ll a,ll b,ll c){
DATA res;
ll bc=b/c,ac=a/c;
ll m=(1ll*n*a+b)/c;
if(!a){
res.f=(n+1)*bc%MOD;
res.g=(n+1)*n%MOD*bc%MOD*inv2%MOD;
res.h=(n+1)*bc%MOD*bc%MOD;
return res;
}
if(a>=c || b>=c){
DATA tmp=Calc(n,a%c,b%c,c);
res.f=(tmp.f+(n+1)*bc%MOD+sum1(n)*ac%MOD)%MOD;
res.g=(tmp.g+sum2(n)*ac%MOD+sum1(n)*bc%MOD)%MOD;
res.h=(tmp.h+2*bc%MOD*tmp.f%MOD+2*ac%MOD*tmp.g%MOD+sum2(n)*ac%MOD*ac%MOD+(n+1)*bc%MOD*bc%MOD+n*(n+1)%MOD*ac%MOD*bc%MOD)%MOD;
return res;
}
DATA tmp=Calc(ll(m-1),c,c-b-1,a);
res.f=((n*m%MOD-tmp.f)%MOD+MOD)%MOD;
res.g=((n*m%MOD*(n+1)%MOD-tmp.h-tmp.f)%MOD+MOD)%MOD*inv2%MOD ;
res.h=((n*m%MOD*(m+1)%MOD-2ll*tmp.g%MOD-2ll*tmp.f%MOD-res.f)%MOD+MOD)%MOD;
return res;
}

int main(){
int cas;scanf("%d",&cas);
ll n,a,b,c;
while(cas--){
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
DATA ans=Calc(n,a,b,c);
printf("%lld %lld %lld\n",ans.f,ans.h,ans.g);
}
return 0;
}

The End

Thanks for reading!

我觉得应该向 OI 界全力推广 OI-wiki ο(=•ω<=)ρ⌒☆