「bsoj4936」「模板题」类欧几里得 - 类欧几里得 附简要学习笔记 | Bill Yang's Blog

「bsoj4936」「模板题」类欧几里得 - 类欧几里得 附简要学习笔记

题目大意

    求:


前置技能

  1. 这个式子显然成立。
  2. 证明:

类欧几里得算法

这是一道类欧几里得的模板题,类欧几里得模板有三种形式:

下文为了方便,记$m=\lfloor\frac{ai+b}c\rfloor$。

推$f$式

先来看最简单的$f$推导。

  • 若$a\ge c$或$b\ge c$
  • $a,b\lt c$然后递归处理即可。

推$g$式

  • 若$a\ge c$或$b\ge c$
  • 若$a,b\lt c$发现这个$g$很麻烦,递归时需要用到$f$和$h$,因此不妨先看看$h$的推导。

推$h$式

  • 若$a\ge c$或$b\ge c$
  • 若$a,b\lt c$
    此时我们需要用到前置技能中将平方展开成求和式的技巧。
    本人采用下标从$1$开始的展开式,当然也可以使用下标从$0$开始的展开式,但与之前的递推式下标不对应,等会儿讲计算方法的时候就不好处理。

计算方法

  1. 按照递归式写出三个函数计算$f,g,h$并互相调用递归。
    直观可行,但会有很多状态被重复计算,时间效率低下。
  2. 逐层递推
    发现每一个$f/g/h(a,b,c,n)$仅与$f/g/h(c,c-b-1,a,m-1)$有关($h(a,b,c,n)$除外),因此我们不妨直接计算$f/g/h(c,c-b-1,a,m-1)$,然后计算出$f/g/h(a,b,c,n)$。
    这样可以有效减少重复状态,时间效率优良。

时间复杂度分析

原式的值仅与$a,b,c$有关,与$n$关系不大。
若采用逐层递推的方法:
仅观察函数的第一/三维,即可发现每次从二元组$(a,c)$变为$(c,a\bmod c)$,因此与欧几里得算法类似,时间复杂度近似与欧几里得算法相同。


总结

类欧几里得算法的思想是将一个多项式转为求和式。
利用$\sum$的交换与除法的蜜汁性质对原式进行变形。
当原式变形到$\sum$与限制条件兼容时,即可去掉$\sum$直接计数。
目标是得到一个范围更小的递归式。


代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1e9+7,inv2=500000004,inv6=166666668;
LL C2(LL n) {
return (n*(n+1)>>1)%mod;
}
LL C6(LL n) {
return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}
void add(LL &x,LL v) {
if(v>=mod)v%=mod;
x+=v;
if(x>=mod)x-=mod;
}
struct Data {
LL f,g,h;
Data(LL _f=0,LL _g=0,LL _h=0):f(_f),g(_g),h(_h) {}
};
Data Euclidean(LL a,LL b,LL c,LL n) {
if(!a&&b<c)return Data();
if(a>=c||b>=c) {
Data now=Euclidean(a%c,b%c,c,n);
n%=mod;
LL _a=a/c,_b=b/c;
add(now.h,_a*_a%mod*C6(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*C6(n)%mod+_b*C2(n)%mod);
return now;
}
LL m=(a*n+b)/c;
Data now,next=Euclidean(c,c-b-1,a,m-1);
n%=mod,m%=mod;
now.f=((n*m%mod-next.f)%mod+mod)%mod;
now.g=((n*(n+1)%mod*m%mod-next.f-next.h)%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;
}
LL a,b,c,l,r;
int main() {
a=Get_Int();
c=Get_Int();
b=Get_Int();
l=Get_Int();
r=Get_Int();
printf("%lld\n",(Euclidean(a,b,c,r).g-Euclidean(a,b,c,l-1).g+mod)%mod);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%