类欧几里得算法

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 3.3k 阅读时长 ≈ 11 分钟
本文记录了类欧的一些性质及其题目

参考博客
参考博客

说是类欧几里得,其实和欧几里得关系不大。只是形式上有点像 ,O(log n)的复杂度。

类欧几里得几何性质:
等价于求y=(ax+b)/c这条直线与x=0和x=n y=0围成的直角梯形上的整点的个数,在直线上的统计在内，在x=0和x=n上的统计在内，在y=0上的不统计

begin:

首先定义三个函数：
$f(a,b,c,n) = \sum_{i=0}^n{\lfloor\frac{ai+b}{c}\rfloor}$

$g(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}$    以上三式都有  

为了方便，我们令

一些不等式：

$a \leq \lfloor \frac{b}{c} \rfloor \Leftrightarrow ac \leq b$

$a \lt \lceil \frac{b}{c} \rceil \Leftrightarrow ac \lt b$

$a \ge \lceil \frac{b}{c} \rceil \Leftrightarrow ac \ge b$

$a \gt \lfloor \frac{b}{c} \rfloor \Leftrightarrow ac \gt b$

$\lceil \frac{b}{c} \rceil = \lfloor \frac{b+c-1}{c}\rfloor $

$\lfloor \frac{b}{c} \rfloor = \lceil \frac{b-c+1}{c}\rceil $

求f:

① $a\ge c 或 b \ge c$

$\lfloor\frac{ai+b}{c}\rfloor \Leftrightarrow \lfloor \frac{(a \% c)i+b\%c]}{c} \rfloor + \lfloor \frac{a}{c} \rfloor i + \lfloor \frac{b}{c}\rfloor$

$f(a,b,c,n) \Leftrightarrow f(a\%b,b\%c,c,n)$ + $\frac{n(n+1)}{2}\lfloor \frac{a}{c}\rfloor$ + $(n+1)\lfloor \frac{b}{c}\rfloor$

②$a\lt c $  and  $ b \lt c $

若a = 0 $\Rightarrow$ $f(a,b,c,n) = 0$

若a $\neq$ 0:

求g：

①$a\ge c 或 b \ge c$

$g(a,b,c,n) = g(a\%c,b\%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\lt c $  and  $ b \lt c $

求h:

①$a\ge c 或 b \ge c$

$h(a,b,c,n)=h(a\%c,b\%c,c,n)+ \frac{n(n+1)(2n+1)}{6}(\frac{a}{c})^2 +(n+1)(\frac{b}{c})^2+2g(a \% c,b \% c,c,n)(\frac{a}{c})+2f(a \% c,b \% c,c,n)(\frac{b}{c})+n(n+1)(\frac{a}{c})(\frac{b}{c})$

②$a\lt c $  and  $ b \lt c $

tips:为了方便,把$n^{2}$拆成$n^2 = 2*\frac{n(n+1)}{2}-n =( 2\sum_{i=0}^{n}i)-n$ 这样做的目的是不会出现$\sum x \sum$的形式

令t$=\lfloor \frac{jc+c-b-1}{a} \rfloor$

所以有$h(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)$

代码：

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
//代码中的h,g的意义对换了一下，懒得改了
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll Mod=998244353;
const ll inv2=499122177,inv6=166374059;
ll S1(ll x){if(x>=Mod)x%=Mod;return (x*(x+1)%Mod)*inv2%Mod;}
ll S2(ll x){if(x>=Mod)x%=Mod;return (x*(x+1)%Mod*(x+x+1)%Mod)*inv6%Mod;}
ll Sqr(ll x){return x*x%Mod;}
struct node{
	ll f,g,h;
	void clear(){f=g=h=0;}
	node(){}
	node(ll a,ll b,ll c):f(a),g(b),h(c){}
	void out(){printf("%lld %lld %lld\n",f,g,h);}
};
node calc(ll a,ll b,ll c,ll n){
	node ans,res;ans.clear();
	ll m,t1,t2,s1,s2;
	if(!n){ans.f=b/c;ans.g=Sqr(b/c);return ans;}
	if(!a){
		t1=b/c;
		ans.f=(n+1ll)*t1%Mod;
		ans.g=(n+1ll)*Sqr(t1)%Mod;
		ans.h=S1(n)*t1%Mod;
		return ans;
	}
	if(a>=c||b>=c){
		t1=a/c;t2=b/c;
		res=calc(a%c,b%c,c,n);
		s1=S1(n);s2=S2(n);
		ans.f=(((s1*t1%Mod)+(n+1ll)*t2%Mod)%Mod+res.f)%Mod;
		ans.g=(((Sqr(t1)*s2%Mod+(n+1ll)*Sqr(t2)%Mod)%Mod)+((t1*t2%Mod)*2ll*s1%Mod+(t1*2ll*res.h%Mod))%Mod+(res.g+t2*2ll*res.f%Mod)%Mod)%Mod;
		ans.h=((s2*t1%Mod+s1*t2%Mod)+res.h)%Mod;
		return ans;
	}
	m=(n*a+b)/c-1;
	res=calc(c,c-b-1,a,m);
	ll w1=n*(m+1)%Mod,w2=n*(n+1)%Mod,w3=m+1;
	if(w3>=Mod)w3%=Mod;
	ans.f=(w1-res.f)%Mod;if(ans.f<0)ans.f+=Mod;
	ans.g=((w1*w3)%Mod-((res.h*2ll%Mod+res.f)%Mod))%Mod;if(ans.g<0)ans.g+=Mod;
	ans.h=((w2*w3)%Mod-(res.f+res.g)%Mod)%Mod*inv2%Mod;if(ans.h<0)ans.h+=Mod;
	return ans;
}
int a,b,c,n,T;
int main(){
	for(scanf("%d",&T);T--;){scanf("%d%d%d%d",&n,&a,&b,&c);calc(a,b,c,n).out();}
	return 0;
}

题目:

1.洛谷模板题
2.loj 一般形式的类欧
3.BZOJ3817
4.[GDOI2018模拟8.8]超级绵羊异或
5.[JZOJ3327]陶陶的难题
6.bzoj2852 vijos1504 强大的区间
7.【JZOJ 3492】【NOIP2013模拟联考12】数数(count)
8.loj6440万能欧几里得
参考代码：
2.https://blog.csdn.net/VictoryCzt/article/details/86099938

万能欧几里得

-------------本文结束感谢您的阅读-------------