Hexo
0%

Posted on In ,
Symbols count in article: 58 Reading time ≈ 1 mins.

费马小定理

若p为素数，$若\ gcd(a,p)\ =\ 1,则a^{p-1}\ \equiv \ 1\ (mod\ p)$

Read more »

Posted on In ,
Symbols count in article: 420 Reading time ≈ 1 mins.

乘法逆元

给定正整数a，b，如果有 $ax\ \equiv \ 1\ (mod\ b)$​，且a与b互质，则称x的最小正整数解为a模b的逆元，（可以理解为倒数)。模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

如果一个线性同余方程$ax\ \equiv \ 1\ (mod\ b)$,则x称为a mod b的逆元

扩展欧几里得法

1
2
3
4
5
6
7
8
void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

快速幂法

1
2
3
4
5
6
7
8
9
int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}
Read more »

Posted on In ,
Symbols count in article: 552 Reading time ≈ 1 mins.

埃式筛

这是一个和辗转相除法一样古老的算法。原理也很简单。
首先将2到n范国内的整数写下来。其中2是最小的素数。将表中所有的2的倍数划去，表中剩下的最小的数宇就是3，他不能被更小的数整除，所以3是素数。
再将表中所有的3的倍数划去
⋯以此类推，_ 如果表中剩余的最小的数是m，那么m就是素数。
然后将表中所有m的倍数划去，像这样反复操作。就能依次枚举n以内的素数

1.求1-20之间的素数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(){
    int cnt=0;//用来计数
    
    bool isprime[21];
    for(int i=0;i<=20;i++)isprime[i]=true;//先全部置为真
 
    isprime[0]=isprime[1]=false;//1 0 不是素数
 
    for(int i=2;i<=20;i++){//从2开始往后筛
        if(isprime[i]){
            for(int j=2*i;j<=20;j+=i){
                isprime[j]=false;
            }
        }
        if(isprime[i]){
            cnt++;//如果是素数 就计数
        }
    }
    printf("%d",cnt);
}
Read more »

Posted on In ,
Symbols count in article: 3.7k Reading time ≈ 3 mins.

最小树形图

有向图上的最小生成树称为最小树形图

Edmonds算法

O(nm)

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
bool solve() {
  ans = 0;
  int u, v, root = 0;
  for (;;) {
    f(i, 0, n) in[i] = 1e100;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      if (u != v && e[i].w < in[v]) {
        in[v] = e[i].w;
        pre[v] = u;
      }
    }
    f(i, 0, m) if (i != root && in[i] > 1e50) return 0;
    int tn = 0;
    memset(id, -1, sizeof id);
    memset(vis, -1, sizeof vis);
    in[root] = 0;
    f(i, 0, n) {
      ans += in[i];
      v = i;
      while (vis[v] != i && id[v] == -1 && v != root) {
        vis[v] = i;
        v = pre[v];
      }
      if (v != root && id[v] == -1) {
        for (int u = pre[v]; u != v; u = pre[u]) id[u] = tn;
        id[v] = tn++;
      }
    }
    if (tn == 0) break;
    f(i, 0, n) if (id[i] == -1) id[i] = tn++;
    f(i, 0, m) {
      u = e[i].s;
      v = e[i].t;
      e[i].s = id[u];
      e[i].t = id[v];
      if (e[i].s != e[i].t) e[i].w -= in[v];
    }
    n = tn;
    root = id[root];
  }
  return ans;
}

Tarjan算法

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define maxn 102
#define INF 0x3f3f3f3f

struct UnionFind {
  int fa[maxn << 1];

  UnionFind() { memset(fa, 0, sizeof(fa)); }

  void clear(int n) { memset(fa + 1, 0, sizeof(int) * n); }

  int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }

  int operator[](int x) { return find(x); }
};

struct Edge {
  int u, v, w, w0;
};

struct Heap {
  Edge *e;
  int rk, constant;
  Heap *lch, *rch;

  Heap(Edge *_e) : e(_e), rk(1), constant(0), lch(NULL), rch(NULL) {}

  void push() {
    if (lch) lch->constant += constant;
    if (rch) rch->constant += constant;
    e->w += constant;
    constant = 0;
  }
};

Heap *merge(Heap *x, Heap *y) {
  if (!x) return y;
  if (!y) return x;
  if (x->e->w + x->constant > y->e->w + y->constant) swap(x, y);
  x->push();
  x->rch = merge(x->rch, y);
  if (!x->lch || x->lch->rk < x->rch->rk) swap(x->lch, x->rch);
  if (x->rch)
    x->rk = x->rch->rk + 1;
  else
    x->rk = 1;
  return x;
}

Edge *extract(Heap *&x) {
  Edge *r = x->e;
  x->push();
  x = merge(x->lch, x->rch);
  return r;
}

vector<Edge> in[maxn];
int n, m, fa[maxn << 1], nxt[maxn << 1];
Edge *ed[maxn << 1];
Heap *Q[maxn << 1];
UnionFind id;

void contract() {
  bool mark[maxn << 1];
  // 将图上的每一个结点与其相连的那些结点进行记录。
  for (int i = 1; i <= n; i++) {
    queue<Heap *> q;
    for (int j = 0; j < in[i].size(); j++) q.push(new Heap(&in[i][j]));
    while (q.size() > 1) {
      Heap *u = q.front();
      q.pop();
      Heap *v = q.front();
      q.pop();
      q.push(merge(u, v));
    }
    Q[i] = q.front();
  }
  mark[1] = true;
  for (int a = 1, b = 1, p; Q[a]; b = a, mark[b] = true) {
    // 寻找最小入边以及其端点，保证无环。
    do {
      ed[a] = extract(Q[a]);
      a = id[ed[a]->u];
    } while (a == b && Q[a]);
    if (a == b) break;
    if (!mark[a]) continue;
    // 对发现的环进行收缩，以及环内的结点重新编号，总权值更新。
    for (a = b, n++; a != n; a = p) {
      id.fa[a] = fa[a] = n;
      if (Q[a]) Q[a]->constant -= ed[a]->w;
      Q[n] = merge(Q[n], Q[a]);
      p = id[ed[a]->u];
      nxt[p == n ? b : p] = a;
    }
  }
}

ll expand(int x, int r);

ll expand_iter(int x) {
  ll r = 0;
  for (int u = nxt[x]; u != x; u = nxt[u]) {
    if (ed[u]->w0 >= INF)
      return INF;
    else
      r += expand(ed[u]->v, u) + ed[u]->w0;
  }
  return r;
}

ll expand(int x, int t) {
  ll r = 0;
  for (; x != t; x = fa[x]) {
    r += expand_iter(x);
    if (r >= INF) return INF;
  }
  return r;
}

void link(int u, int v, int w) { in[v].push_back({u, v, w, w}); }

int main() {
  int rt;
  scanf("%d %d %d", &n, &m, &rt);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    link(u, v, w);
  }
  // 保证强连通
  for (int i = 1; i <= n; i++) link(i > 1 ? i - 1 : n, i, INF);
  contract();
  ll ans = expand(rt, n);
  if (ans >= INF)
    puts("-1");
  else
    printf("%lld\n", ans);
  return 0;
}
Read more »

Posted on In ,
Symbols count in article: 2.1k Reading time ≈ 2 mins.

最小生成树

prim

稀疏图，采用邻接矩阵进行存储边之间的关系

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
// prim 算法求最小生成树 

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 505;

int a[maxn][maxn];

int vis[maxn],dist[maxn];

int n,m;

int u,v,w;

long long sum = 0;

int prim(int pos) {
	dist[pos] = 0;
	// 一共有 n 个点,就需要 遍历 n 次,每次寻找一个权值最小的点,记录其下标
	for(int i = 1; i <= n; i ++) {
		int cur = -1;
		for(int j = 1; j <= n; j ++) {
			if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {
				cur = j;
			}
		}
		// 这里需要提前终止
		if(dist[cur] >= INF) return INF;
		sum += dist[cur];
		vis[cur] = 1;
		for(int k = 1; k <= n; k ++) {
		    // 只更新还没有找到的最小权值
			if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);
		}
	}
	return sum;
}

int main(void) {
	scanf("%d%d",&n,&m);
	memset(a,0x3f,sizeof(a));
	memset(dist,0x3f,sizeof(dist));
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d%d",&u,&v,&w);
		a[u][v] = min(a[u][v],w);
		a[v][u] = min(a[v][u],w);
	}
	int value = prim(1);
	if(value >= INF) puts("impossible");
	else printf("%lld\n",sum);
	return 0;
}

kruskal

稠密图，采用邻接表进行存储边之间的关系

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
// Kruskal 算法求最小生成树 

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10; 

struct node {
	int x,y,z;
}edge[maxn];

bool cmp(node a,node b) {
	return a.z < b.z;
}

int fa[maxn];

int n,m;

int u,v,w; 

long long sum;

int get(int x) {
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

int main(void) {
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i ++) {
		scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
	}
	for(int i = 0; i <= n; i ++) {
		fa[i] = i;
	}
	sort(edge + 1,edge + 1 + m,cmp);
	// 每次加入一条最短的边
	for(int i = 1; i <= m; i ++) {
		int x = get(edge[i].x);
		int y = get(edge[i].y);
		if(x == y) continue;
		fa[y] = x;
		sum += edge[i].z;
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		if(i == fa[i]) ans ++;
	}
	if(ans > 1) puts("impossible");
	else printf("%lld\n",sum);
	return 0;
}

Read more »