Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

类欧几里得算法

算法

发布于：Apr 30, 2022

更新于：Aug 13, 2024

次浏览

类欧几里得算法之所以得名是因为其算法复杂度证明与扩展欧几里得算法类似。

我认为类欧更偏向于是一种思想。

其主要思想就是寻找可以简便计算的边界，然后通过化式子将不同情况化为边界递归计算。

通过几个具体的例子，可以更好地理解其思想。

P5170 【模板】类欧几里得算法

推导

\[ 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}^N i\lfloor \frac{ai+b}{c}\rfloor \]

\[ f(a,b,c,N)=\begin{cases}(N+1)\lfloor\frac{b}{c}\rfloor&a=0\\\frac{N(N+1)}{2}\lfloor\frac{a}{c}\rfloor+(N+1)\lfloor\frac{b}{c}\rfloor+f(a\bmod c,b\bmod c,c,N)&a\ge c\ or\ b\ge c\\NM-f(c,c-b-1,a,M-1),M=\lfloor\frac{aN+b}{c}\rfloor &otherwise\end{cases} \]

\[ 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\ or\ b\ge c\\NM(M+1)-f(a,b,c,N)-2h(c,c-b-1,a,M-1)-2f(c,c-b-1,a,M-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\ or\ b\ge c\\\frac{1}{2}[MN(N+1)-g(c,c-b-1,a,M-1)-f(c,c-b-1,a,M-1)]&otherwise\end{cases} \]

代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<tuple>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
const int mod=998244353;
tuple<int,int,int> calc(long long a,long long b,long long c,long long n){
	int f,g,h,fn,gn,hn;
	if(!a){
		fn=(n+1)*(b/c)%mod;
		gn=(n+1)*(b/c)%mod*(b/c)%mod;
		hn=n*(n+1)%mod*((mod+1)>>1)%mod*(b/c)%mod;
	}else if(a>=c or b>=c){
		tie(f,g,h)=calc(a%c,b%c,c,n);
		fn=(n*(n+1)%mod*((mod+1)>>1)%mod*(a/c)%mod+(n+1)*(b/c)%mod+f)%mod;
		gn=(n*(n+1)%mod*(2*n+1)%mod*((mod+1)/6)%mod*(a/c)%mod*(a/c)%mod+(n+1)*(b/c)%mod*(b/c)%mod+n*(n+1)%mod*(a/c)%mod*(b/c)%mod+2*(b/c)%mod*f%mod+g+2*(a/c)%mod*h%mod)%mod;
		hn=(n*(n+1)%mod*(2*n+1)%mod*((mod+1)/6)%mod*(a/c)%mod+n*(n+1)%mod*((mod+1)>>1)%mod*(b/c)%mod+h)%mod;
	}else{
		tie(f,g,h)=calc(c,c-b-1,a,(a*n+b)/c-1);
		fn=(n*((a*n+b)/c)%mod-f+mod)%mod;
		gn=(n*((a*n+b)/c)%mod*((a*n+b)/c+1)%mod-fn+mod-2*f%mod+mod-2*h%mod+mod)%mod;
		hn=(n*(n+1)%mod*((a*n+b)/c)%mod*((mod+1)>>1)%mod-f*((mod+1ll)>>1)%mod+mod-g*((mod+1ll)>>1)%mod+mod)%mod;
	}
	return tie(fn,gn,hn);
}
signed main(){
	int T=read(),n,a,b,c,f,g,h;
	while(T--) n=read(),a=read(),b=read(),c=read(),tie(f,g,h)=calc(a,b,c,n),printf("%d %d %d\n",f,g,h);
	return 0;
}

P5171 Earthquake

题意

求满足 \(ax+by⩽c\) 的非负整数解的个数。

推导

\[ y⩽\left\lfloor\frac{c-ax}{b}\right\rfloor\\ ans=\sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor\frac{c-ax}{b}\right\rfloor+1\\ =\sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor\frac{c+(b-a)x}{b}\right\rfloor-x+1\\ (\sum_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor\frac{c+(b-a)x}{b}\right\rfloor)-\frac{\left\lfloor\frac{c}{a}\right\rfloor(\left\lfloor\frac{c}{a}\right\rfloor+1)}{2}+\left\lfloor\frac{c}{a}\right\rfloor+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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
long long f(long long a,long long b,long long c,long long n){
	if(!a) return (n+1)*(b/c);
	if(a>=c or b>=c) return n*(n+1)/2*(a/c)+(n+1)*(b/c)+f(a%c,b%c,c,n);
	return n*((a*n+b)/c)-f(c,c-b-1,a,(a*n+b)/c-1);
}
signed main(){
	int a=read(),b=read(),c=read();
	if(a>b)swap(a,b);
	printf("%lld\n",f(b-a,c,b,c/a)-1ll*(c/a)*(c/a+1)/2+c/a+1);
}

P5172 Sum

推导

\[ ans=\sum_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor}\\=\sum_{d=1}^n1-2(\lfloor d\sqrt r\rfloor\bmod 2)\\=\sum_{d=1}^n1-2(\lfloor d\sqrt r\rfloor-2\lfloor \frac{d\sqrt r}2\rfloor) \]

\[ f(a,b,c,n)=\sum_{d=1}^n\lfloor\frac{a\sqrt r+b}{c}d\rfloor \]

当 \(\lfloor\frac{a\sqrt r+b}{c}\rfloor\ge1\) 时， \[ f(a,b,c,n)=\sum_{d=1}^n\lfloor\frac{a\sqrt r+b}{c}d\rfloor\\=\sum_{d=1}^n\lfloor\frac{a\sqrt r+b-c\lfloor\frac{a\sqrt r+b}{c}\rfloor}{c}d+\lfloor\frac{a\sqrt r+b}{c}\rfloor d\rfloor\\=\sum_{d=1}^nf(a,b-c\lfloor\frac{a\sqrt r+b}{c}\rfloor,c,n)+\frac 1 2n(n+1)\lfloor\frac{a\sqrt r+b}{c}\rfloor \] 当 \(\lfloor\frac{a\sqrt r+b}{c}\rfloor=0\) 时, \[ f(a,b,c,n)=\sum_{d=1}^n\lfloor\frac{a\sqrt r+b}{c}d\rfloor\\=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{a\sqrt r+b}{c}n\rfloor}[p\le\frac{a\sqrt r+b}{c}d]\\=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{a\sqrt r+b}{c}n\rfloor}[d\ge\frac{cp}{a\sqrt r+b}]\\=\sum_{p=1}^{\lfloor\frac{a\sqrt r+b}{c}n\rfloor} n-\lfloor\frac{cp}{a\sqrt r+b}\rfloor\\\texttt{（无理数，大于等于与大于等价）}\\=\lfloor\frac{a\sqrt r+b}{c}n\rfloor n-\sum_{p=1}^{\lfloor\frac{a\sqrt r+b}{c}n\rfloor}\lfloor\frac{c(a\sqrt r -b)}{a^2r-b^2}p\rfloor\\=\lfloor\frac{a\sqrt r+b}{c}n\rfloor n-f(ac,-bc,a^2r-b^2,\lfloor\frac{a\sqrt r+b}{c}n\rfloor) \]

\[ ans=1-2f(1,0,1,n)+4f(1,0,2,n) \]

代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
double sr;
int r;
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long f(long long a,long long b,long long c,long long n){
	if(!n) return 0;
	long long g=gcd(gcd(a,b),c);a/=g,b/=g,c/=g;
	long long k=(a*sr+b)/c;
	if(k) return f(a,b-c*k,c,n)+n*(n+1)/2*k;
	return (long long)((a*sr+b)/c*n)*n-f(a*c,-b*c,a*a*r-b*b,(long long)((a*sr+b)/c*n));
}
signed main(){
	int T=read(),n;
	while(T--){
		n=read(),r=read();sr=sqrt(r);
		if((int)sr*(int)sr==r) printf("%d\n",((int)sr&1)?-(n&1):n);
		else printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
	}
	return 0;
}

P5179 Fraction

推导

\[ f(a,b,p,q,c,d)\begin{cases}q=1,p=\left\lfloor\frac{a}{c}\right\rfloor+1&\left\lfloor\frac{a}{c}\right\rfloor+1⩽\left\lceil\frac{c}{d}\right\rceil-1\\p=1,q=\left\lfloor\frac{d}{c}\right\rfloor+1&a=0\\ f(b,a,q,p,d,c)&a⩽b \and c⩽d\\f(a\mod b,b,p,q,c-\left\lfloor\frac{a}{b}\right\rfloor d,d),p=p+\left\lfloor\frac{a}{b}\right\rfloor q&a\ge b\end{cases} \]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
using namespace std;
void calc(long long a,long long b,long long &p,long long &q,long long c,long long d){
	if(a/b+1<=(c+d-1)/d-1) p=a/b+1,q=1;
	else if(!a) p=1,q=d/c+1;
	else if(a<=b and c<=d) calc(d,c,q,p,b,a);
	else calc(a%b,b,p,q,c-a/b*d,d),p+=a/b*q;
}
signed main(){
	long long a,b,c,d,p,q;
	while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)) calc(a,b,p,q,c,d),printf("%lld/%lld\n",p,q);
	return 0;
}

更新于：Aug 13, 2024

博客园

OI

数论

给小狼留言