ACM经典代码数论_ 图论_几何_组合_数值等

目录

一．数论.............................................................................................................................................4

1.阶乘最后非零位......................................................................................................................4

2. 模线性方程(组)......................................................................................................................4

3. 素数表.....................................................................................................................................6

4. 素数随机判定(miller_rabin)..................................................................................................6

5. 质因数分解.............................................................................................................................7

6. 最大公约数欧拉函数.............................................................................................................8

6. 一般图匹配(邻接表形式)....................................................................................................12

7. 一般图匹配(邻接表形式,邻接阵接口)...............................................................................13

8. 一般图匹配(邻接阵形式)....................................................................................................14

9. 一般图匹配(正向表形式)....................................................................................................15

三．图论_生成树.............................................................................................................................16

1. 最小生成树(kruskal 邻接表形式).......................................................................................16

2. 最小生成树(kruskal 正向表形式).......................................................................................18

3. 最小生成树(prim+binary_heap 邻接表形式).....................................................................19

4. 最小生成树(prim+binary_heap 正向表形式).....................................................................20

5. 最小生成树(prim+mapped_heap 邻接表形式)...................................................................21

3. 上下界最小流(邻接表形式)................................................................................................29

4. 上下界最小流(邻接阵形式)................................................................................................30

5. 最大流(邻接表形式)............................................................................................................31

6. 最大流(邻接表形式,邻接阵接口).......................................................................................32

7. 最大流(邻接阵形式)............................................................................................................33

8. 最大流无流量(邻接阵形式)................................................................................................34

9. 最小费用最大流(邻接阵形式)............................................................................................35

五. 图论_最短路径...........................................................................................................................36

1. 最短路径(单源 bellman_ford 邻接阵形式).........................................................................36

2. 最短路径(单源 dijkstra_bfs 邻接表形式)...........................................................................37

8. 最短路径(单源 dijkstra 邻接阵形式)..................................................................................43

9. 最短路径(多源 floyd_warshall 邻接阵形式)......................................................................43

六. 图论_连通性...............................................................................................................................44

1. 无向图关键边(dfs 邻接阵形式)..........................................................................................44

2. 无向图关键点(dfs 邻接阵形式)..........................................................................................44

3. 无向图块(bfs 邻接阵形式)..................................................................................................45

4. 无向图连通分支(bfs 邻接阵形式)......................................................................................46

5. 无向图连通分支(dfs 邻接阵形式)......................................................................................47

6. 有向图强连通分支(bfs 邻接阵形式)..................................................................................47

7. 有向图强连通分支(dfs 邻接阵形式)..................................................................................48

5. 最佳边割集...........................................................................................................................53

6. 最佳顶点割集.......................................................................................................................54

7. 最小边割集...........................................................................................................................56

8. 最小顶点割集.......................................................................................................................57

9. 最小路径覆盖.......................................................................................................................58

八. 图论_NP 搜索.............................................................................................................................59

1. 最大团(n 小于 64)(faster).....................................................................................................59

2. 最大团...................................................................................................................................61

九. 组合.............................................................................................................................................62

1. 排列组合生成.......................................................................................................................62

1. 定积分计算(Romberg).........................................................................................................67

2. 多项式求根(牛顿法)............................................................................................................68

3. 周期性方程(追赶法)............................................................................................................70

十一. 几何.........................................................................................................................................71

1. 多边形...................................................................................................................................71

2. 多边形切割...........................................................................................................................74

3. 浮点函数...............................................................................................................................75

4. 几何公式...............................................................................................................................81

5. 面积.......................................................................................................................................83

9. 凸包(graham)........................................................................................................................96

10. 网格(pick)...........................................................................................................................98

11. 圆.........................................................................................................................................99

12. 整数函数...........................................................................................................................101

13. 注意...................................................................................................................................104

十二. 结构.......................................................................................................................................105

1. 并查集.................................................................................................................................105

2. 并查集扩展(friend_enemy)................................................................................................105

3. 堆(binary)............................................................................................................................106

4. 堆(mapped)..........................................................................................................................106

十三. 其他.......................................................................................................................................114

1. 分数.....................................................................................................................................114

2. 矩阵.....................................................................................................................................116

3. 日期.....................................................................................................................................118

4. 线性方程组(gauss).............................................................................................................120

5. 线性相关.............................................................................................................................121

十四. 应用.......................................................................................................................................122

1. joseph...................................................................................................................................122

2. N 皇后构造解.....................................................................................................................123

3. 布尔母函数.........................................................................................................................124

10. 最长子序列.......................................................................................................................129

11. 最大子串匹配...................................................................................................................130

12. 最大子段和.......................................................................................................................131

13. 最大子阵和.......................................................................................................................131

1.阶乘最后非零位

int len=strlen(buf),a[MAXN],i,c,ret=1;

if (len==1)

return mod[buf[0]-'0'];

for (i=0;i<len;i++)

a[i]=buf[len-1-i]-'0';

for (;len;len-=!a[len-1]){

ret=ret*mod[a[1]%2*10+a[0]]%5;

for (c=0,i=len-1;i>=0;i--)

c=c*10+a[i],a[i]=c/5,c%=5;

}

typedef long long i64;

#endif

//扩展 Euclid 求解 gcd(a,b)=ax+by

int ext_gcd(int a,int b,int& x,int& y){

int t,ret;

if (!b){

x=1,y=0;

return a;

}

ret=ext_gcd(b,a%b,x,y);

for (;a;a>>=1,m*=m)

if (a&1)

ret*=m;

return ret;

}

//计算幂取模 a^b mod n, O(logb)

int modular_exponent(int a,int b,int n){ //a^b mod n

int ret=1;

for (;b;b>>=1,a=(int)((i64)a)*a%n)

if (b&1)

ret=(int)((i64)ret)*a%n;

//要求 n>0,解的范围 0..n-1

return 0;

e=(x*(b/d)%n+n)%n;

for (i=0;i<d;i++)

sol[i]=(e+i*(n/d))%n;

return d;

}

// x = b[0] (mod w[0])

// x = b[1] (mod w[1])

// ...

// x = b[k-1] (mod w[k-1])

//要求 w[i]>0,w[i]与 w[j]互质,解的范围 1..n,n=w[0]*w[1]*...*w[k-1]