发表更新C++算法1 分钟读完 (大约116个字)

Cpp算法-字符串算法-KMP

例：洛谷P3375

说明

pre()求前缀数组

kmp()匹配字符串

实现

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
char s1[1000010], s2[1000010];
int nxt[1000010], l1, l2;

void pre()
{
    nxt[1] = 0;
    int j = 0;
    for (int i = 1; i < l2; ++i)
    {
        while (j > 0 && s2[j + 1] != s2[i + 1]) j = nxt[j];
        if (s2[j + 1] == s2[i + 1]) j++;
        nxt[i + 1] = j;
    }
}

void kmp()
{
    int j = 0;
    for (int i = 0; i < l1; ++i)
    {
        while (j > 0 && s2[j + 1] != s1[i + 1]) j = nxt[j];
        if (s2[j + 1] == s1[i + 1]) j++;
        if (j == l2)
        {
            printf("%d\n", i - l2 + 2);
            j = nxt[j];
        }
    }
}

int main()
{
    cin >> s1 + 1;
    cin >> s2 + 1;
    l1 = strlen(s1 + 1);
    l2 = strlen(s2 + 1);
    pre();
    kmp();
    return 0;
}
发表更新C++算法1 分钟读完 (大约145个字)

Cpp算法-字符串算法-哈希表

例：洛谷P4305

说明

hash[]哈希表

find(int x)查找哈希表中 $x$ 的位置

push(int x)将 $x$ 插入到哈希表中

check(int x)查找 $x$ 是否在哈希表中

实现

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
#define p 100003
#define hash(a) a%p

int h[p], t, n, x;

int find(int x)
{
    int y;
    if (x < 0) y = hash(-x);
    else y = hash(x);
    while (h[y] && h[y] != x) y = hash(++y);
    return y;
}

void push(int x)
{
    h[find(x)] = x;
}

bool check(int x)
{
    return h[find(x)] == x;
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        memset(h, 0, sizeof(h));
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d", &x);
            if (!check(x))
            {
                printf("%d ", x);
                push(x);
            }
        }
        printf("\n");
    }
    return 0;
}
发表更新C++算法1 分钟读完 (大约217个字)

Cpp算法-字符串算法-字符串哈希

例：洛谷P3370

单哈希(自然溢出)

1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ULL;
ULL base = 131, a[10010];
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = Ans * base + (ULL)s[i];
    return Ans & 0x7fffffff;
}

单哈希(单模数)

1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 19260817;
char s[10010];

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod;
    return Ans;
}

单哈希(大模数)

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef unsigned long long ULL;
ULL base = 131, a[10010], mod = 212370440130137957LL;
char s[10010];
int prime = 233317;

ULL hash(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; ++i)
        Ans = (Ans * base + (ULL)s[i]) % mod + prime;
    return Ans;
}

双哈希

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
typedef unsigned long long ULL;
ULL base = 131, mod1=19260817, mod2=19660813;
char s[10010];
struct data
{
    ULL x,y;
}a[10010];

ULL hash1(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod1;
    return Ans;
}

ULL hash2(char* s)
{
    int len = strlen(s);
    ULL Ans = 0;
    for (int i = 0; i < len; i++)
        Ans = (Ans * base + (ULL)s[i]) % mod2;
    return Ans;
}
发表更新C++算法几秒读完 (大约55个字)

Cpp算法-数论-线性筛素数

说明

p[] 最终结果

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool vis[N];
int p[N], cnt;

void get_prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i])
            p[++cnt] = i;
        for (int j = 1; j <= cnt; ++j)
        {
            int v = i * p[j];
            if (v >= N) break;
            vis[v] = true;
            if (i % p[j] == 0) continue;
        }
    }
}
发表更新C++算法1 分钟读完 (大约188个字)

Cpp算法-图论-Floyd

说明

n, m, G[][]点数、边数、邻接矩阵

dist[][]每对顶点间路径长度

pre[][]每对顶点之间路径

make()建图

实现

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
const int maxn = 110;
int n, m, G[maxn][maxn], dist[maxn][maxn], pre[maxn][maxn];

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Floyd()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            dist[i][j] = G[i][j];
            pre[i][j]  = i;
        }
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j]  = pre[k][j];
                }
            }
        }
    }
    return;
}
发表更新C++算法2 分钟读完 (大约244个字)

Cpp算法-图论-欧拉回路

邻接矩阵

说明

G[][]邻接矩阵

deg[]度

ans[]欧拉回路

n, e点数、边数

实现

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
int G[maxn][maxn], deg[maxn], ans[maxn];
int n, e, x, y, ansi, s;

void Euler(int i)
{
	for (int j = 1; j <= n; ++j)
	{
		if (G[i][j])
		{
			G[i][j] = G[j][i] = 0;
			Euler(j);
		}
	}
	ans[++ansi] = i;
}

int main()
{
	scanf("%d %d", &n, &e);
	for (int i = 1; i <= e; ++i)
	{
		scanf("%d %d", &x, &y);
		G[x][y] = G[y][x] = 1;
		deg[x]++;
		deg[y]++;
	}
	s = 1;
	for (int i = 1; i <= n; ++i)
		if (deg[i] % 2 == 1)
			s = i;
	Euler(s);
	for (int i = 1; i <= ansi; ++i)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}

链式前向星

说明

n, m点数、边数

head, edge[]链式前向星

ans[], ansi路径、数组大小

vis[]记录

make()建图

实现

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
int head[maxn];
struct Node
{
	int to, next;
}edge[maxm];

void make()
{
	scanf("%d %d", &n, &m);
	for (int k = 1; k <= m; ++k)
	{
		int i, j;
		scanf("%d %d", &i, &j);
		edge[k].to = i;
		edge[k].next = head[i];
		head[i] = k;
	}
	return;
}

int ans[maxm];
int ansi = 0;
bool vis[2 * maxm];

void dfs(int now)
{
    for (int k = head[now]; k != 0; k = edge[k].next)
	{
        if (!vis[k])
        {
            vis[k] = true;
            vis[k ^ 1] = true;
            dfs(edge[k].to);
            ans[ansi++] = k;
        }
	}
}
发表更新C++算法1 分钟读完 (大约133个字)

Cpp算法-动态规划

待完成

多阶段过程决策的最优化问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
graph LR
    A --5--> B1
    A --3--> B2
    B1 --1--> C1
    B1 --6--> C2
    B1 --3--> C3
    B2 --8--> C2
    B2 --4--> C4
    C1 --5--> D1
    C1 --6--> D2
    C2 --5--> D1
    C3 --8--> D3
    C4 --3--> D3
    D1 --3--> E
    D2 --4--> E
    D3 --3--> E

!!! tldr “题目及注解”
求上图从 $A$ 到 $E$ 的最短距离


$K$: 阶段

$D(X_I, (X+1)_J)$: 从 $X_I$ 到 $(X+1)_J$ 的距离

$F_K(X_I)$: $K$ 阶段下 $X_I$ 到终点 $E$ 的最短距离

倒推:
$$
K=4\qquad F_4(D_1)=3\qquad F_4(D_2)=4\qquad F_4(D_3)=3
$$
$$
K=5\qquad F_3(C_1)=min(D(C_1,D_1)+F_4(D_1),D(C_1,D_2)+F_4(D_2))=min(5+3,6+4)=8
F_3(C_2)
$$

发表更新C++算法2 分钟读完 (大约360个字)

Cpp算法-图论-Dijkstra

说明

n, m点数、边数

G[][]邻接矩阵存图

dist[]路径长度

pre[]路径

make()建图

实现

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
const int maxn = 10010;
int n, m, G[maxn][maxn], dist[maxn], pre[maxn], s;

void make()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            G[i][j] = INT_MAX;
    for (int i = 1; i <= n; ++i) G[i][i] = 0;
    for (int i = 1; i <= m; ++i)
    {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        G[from][to] = w;
    }
    return;
}

void Dijkstra()
{
    int k, min;
    bool p[maxn];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = false;
        if (i != s)
        {
            dist[i] = G[s][i];
            pre[i]  = s;
        }
    }
    dist[s] = 0; p[s] = true;
    for (int i = 1; i <= n - 1; ++i)
    {
        min = INT_MAX; k = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        if (k == 0) return;
        p[k] = true;
        for (int j = 1; j <= n; ++j)
        {
            if (!p[j] && G[k][j] != INT_MAX && dist[j] > dist[k] + G[k][j])
            {
                dist[j] = dist[k] + G[k][j];
                pre[j] = k;
            }
        }
    }
    return;
}

堆优化(链式前向星)

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
struct Edge
{
    int to, nxt, t;
}edge[maxm << 1];
int head[maxn], cnt;
void add(int a, int b, int t)
{
    edge[++cnt].to  = b;
    edge[cnt].nxt = head[a];
    edge[cnt].t   = t;
    head[a]       = cnt;
}

struct heap
{
    int u, d;
    bool operator < (const heap& a) const
    {
        return d > a.d;
    }
};

void Dijkstra()
{
    priority_queue<heap> q;
    for (int i = 0; i <= n; ++i) dist[i] = INF;
    dist[1] = 0;
    q.push((heap){1, 0});
    while (!q.empty())
    {
        heap top = q.top();
        q.pop();
        int tx = top.u;
        int td = top.d;
        if (td != dist[tx]) continue;
        for (int i = head[tx]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (dist[v] > dist[tx] + edge[i].t)
            {
                dist[v] = dist[tx] + edge[i].t;
                dy[v] = i; 
                dx[v] = tx;    //记录路径
                q.push((heap){v, dist[v]});
            }
        }
    }
}
路径
1
2
3
4
5
6
int q = n, p[maxm];
while (q != 1)
{
    p[++tot] = dy[q];
    q = dx[q];
}
发表更新C++算法几秒读完 (大约95个字)

Cpp算法-树状数组

树状数组

模板：洛谷P3374

说明

tree[]树状数组

lowbit(int)神奇的函数

add(int x, int k)第 $x$ 个数加上 $k$

sum(int x)前 $x$ 个数的和

实现

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
int tree[2000010];

int lowbit(int k)
{
    return k & -k;
}

void add(int x, int k)
{
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
发表更新C++算法5 分钟读完 (大约815个字)

Cpp算法-大整数类

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
#include<string>
#include<iostream>
#include<iosfwd>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxl = 5000;
#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b

class BigInteger
{
	public:
		int len, s[maxl];
		
		BigInteger();
		BigInteger(const char*);
		BigInteger(int);
		bool sign;
		string toStr() const;
		friend istream& operator>>(istream&, BigInteger&);
		friend ostream& operator<<(ostream&, BigInteger&);

		BigInteger operator=(const char*);
		BigInteger operator=(int);
		BigInteger operator=(const string);

		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator>(const BigInteger&) const;
		bool operator>=(const BigInteger&) const;
		bool operator==(const BigInteger&) const;
		bool operator!=(const BigInteger&) const;

		BigInteger operator+(const BigInteger&) const;
		BigInteger operator++();
		BigInteger operator++(int);
		BigInteger operator+=(const BigInteger&);
		BigInteger operator-(const BigInteger&) const;
		BigInteger operator--();
		BigInteger operator--(int);
		BigInteger operator-=(const BigInteger&);
		BigInteger operator*(const BigInteger&) const;
		BigInteger operator*(const int num) const;
		BigInteger operator*=(const BigInteger&);
		BigInteger operator/(const BigInteger&) const;
		BigInteger operator/=(const BigInteger&);

		BigInteger operator%(const BigInteger&) const;
		BigInteger factorial() const;
		BigInteger Sqrt() const;
		BigInteger Pow(const BigInteger&) const;

		void clean();
		~BigInteger;
};


BigInteger::BigInteger()
{
	memset(s, 0, sizeof(s));
	len = 1;
	sign = 1;
}

BigInteger::BigInteger(const char *num)
{
	*this = num;
}

BigInteger::BigInteger(int num)
{
	*this = num;
}

string BigInteger::toStr() const
{
	string res;
	res = "";
	for (int i = 0; i < len; ++i)
		res = (char)(s[i] + '0') + res;
	if (res == "") res = "0";
	if (!sign && res != "0") res = "-" + res;
	return res;
}

istream& operator>>(istream& in, BigInteger& num)
{
	string str;
	in>>str;
	num = str;
	return in;
}

ostream& operator<<(ostream& out, BigInteger& num)
{
	out<<num.toStr();
	return out;
}

BigInteger BigInteger::operator=(const char* num)
{
	memset(s, 0, sizeof(s));
	char a[maxl] = "";
	if (num[0] != "-")
		strcpy(a, num);
	else
		for (int i = 1; i < strlen(num); ++i)
			a[i - 1] = num[i];
	sign = !(num[0] == "-");
	len = strlen(a);
	for (int i = 0; i < strlen(a); ++i)
		s[i] = a[len - i - 1] - 48;
	return *this;
}

BigInteger BigInteger::operator=(int num)
{
	if (num < 0)
		sign = 0, num = -num;
	else
		sign = 1;
	char temp[MAX_L];
	sprintf(temp, "%d", num);
	*this = temp;
	return *this;
}

BigInteger BigInteger::operator=(const string num)
{
	const char* tmp;
	tmp = num.c_str();
	*this = tmp;
	return *this;
}

bool BigInteger::operator<(const BigInteger& num) const
{
	if (sign^num.sign)
		return num.sign;
	if (len != num.len)
		return len < num.len;
	for (int i = len - 1; i >= 0; --i)
		if (s[i] != num.s[i])
			return sign ? (s[i] < num.s[i]) : (s[i] > num.s[i])
	return !sign;
}

bool BigInteger::operator>(const BigInteger& num) const
{
	return num < *this;
}

bool BigInteger::operator<=(const BigInteger& num) const
{
	return !(*this > num);
}

bool BigInteger::operator>=(const BigInteger& num) const
{
	return !(*this < num);
}

bool BigInteger::operator!=(const BigInteger& num) const
{
	return *this > num || *this < num;
}

bool BigInteger::operator==(const BigInteger& num) const
{
	return !(num != *this);
}

BigInteger BigInteger::operator+(const BigInteger& num) const
{
	 if (sign^num.sign)
	 {
		 BigInteger tmp = sign ? num : *this;
		 tmp.sign = 1;
		 return sign ? *this - tmp : num - tmp;
	 }
	 BigInteger result;
	 result.len = 0;
	 int temp = 0;
	 for (int i = 0; temp || i < (max(len, num.len)); i++)
	 {
		 int t = s[i] + num.s[i] + temp;
		 result.s[result.len++] = t % 10;
		 temp = t / 10;
	 }
	 result.sign = sign;
	 return result;
}

BigInteger BigInteger::operator++()
{
	*this = *this + 1;
	return *this;
}

BigInteger BigInteger::operator++(int)
{
	BigInteger old = *this;
	++(*this);
	return old;
}

BigInteger BigInteger::operator+=(const BigInteger& num)
{
	*this = *this + num;
	return *this;
}

BigInteger BigInteger::operator-(const BigInteger& num) const
{
	 BigInteger b = num, a = *this;
	 if (!num.sign && !sign)
	 {
		 b.sign = 1;
		 a.sign = 1;
		 return b - a;
	 }
	 if (!b.sign)
	 {
		 b.sign = 1;
		 return a + b;
	 }
	 if (!a.sign)
	 {
		 a.sign = 1;
		 b = BigInteger(0) - (a + b);
		 return b;
	 }
	 if (a < b)
	 {
		 BigInteger c = (b - a);
		 c.sign = false;
		 return c;
	 }
	 BigInteger result;
	 result.len = 0;
	 for (int i = 0, g = 0; i < a.len; i++)
	 {
		 int x = a.s[i] - g;
		 if (i < b.len) x -= b.s[i];
		 if (x >= 0) g = 0;
		 else
		 {
			 g = 1;
			 x += 10;
		 }
		 result.s[result.len++] = x;
	 }
	 result.clean();
	 return result;
}

BigInteger BigInteger::operator--()
{
	*this = *this - 1;
	return *this;
}

BigInteger BigInteger::operator--(int)
{
	BigInteger old = *this;
	--(*this);
	return old;
}

BigInteger BigInteger::operator-=(const BigInteger& num)
{
	*this = *this - num;
	return *this;
}

BigInteger BigInteger::operator*(const BigInteger& num) const
{
	BigInteger result;
	result.len = len + num.len;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < num.len; j++)
			result.s[i + j] += s[i] * num.s[j];
	for (int i = 0; i < result.len; i++)
	{
		 result.s[i + 1] += result.s[i] / 10;
		 result.s[i] %= 10;
	}
	result.clean();
	result.sign = !(sign^num.sign);
	return result;
}

BigInteger BigInteger::operator*(const int num) const
{
	BigInteger x = num;
	BigInteger z = *this;
	return *this;
}

BigInteger BigInteger::operator/(const BigInteger& num) const
{
	 BigInteger ans;
	 ans.len = len - num.len + 1;
	 if (ans.len < 0)
	 {
		 ans.len = 1;
		 return ans;
	 }
	 BigInteger divisor = *this, divid = num;
	 divisor.sign = divid.sign = 1;
	 int k = ans.len - 1;
	 int j = len - 1;
	 while (k >= 0)
	 {
		 while (divisor.s[j] == 0) j--;
		 if (k > j) k = j;
		 char z[MAX_L];
		 memset(z, 0, sizeof(z));
		 for (int i = j; i >= k; i--)
			 z[j - i] = divisor.s[i] + '0';
			 BigInteger dividend = z;
			 if (dividend < divid) { k--; continue; }
			 int key = 0;
			 while (divid*key <= dividend) key++;
			 key--;
			 ans.s[k] = key;
			 BigInteger temp = divid*key;
			 for (int i = 0; i < k; i++)
				 temp = temp * 10;
				 divisor = divisor - temp;
				 k--;
	 }
	 ans.clean();
	 ans.sign = !(sign^num.sign);
	 return ans;
}

BigInteger BigInteger::operator/=(const BigInteger& num)
{
	*this = *this / num;
	return *this;
}

BigInteger BigInteger::operator%(const BigInteger& num) const
{
	BigInteger a = *this, b = num;
	a.sign = b.sign = 1;
	BigInteger result, temp = a / b*b;
	result = a - temp;
	result.sign = sign;
	return result;
}

BigInteger BigInteger::Pow(const BigInteger& num) const
{
	BigInteger result = 1;
	for (BigInteger i = 0; i < num; i++)
		result = result * (*this);
		return result;
}

BigInteger BigInteger::factorial() const
{
	BigInteger result = 1;
	for (BigInteger i = 1; i <= *this; i++)
		result *= i;
	return result;
}

void BigInteger::clean()
{
	if (len == 0) len++;
	while (len > 1 && s[len - 1] == '\0')
		len--;
}

BigInteger BigInteger::Sqrt() const
{
	if(*this < 0) return - 1;
	if(*this <= 1)return *this;
	BigInteger l = 0, r = *this, mid;
	while(r - l > 1)
	{
		mid = (l + r) / 2;
		if(mid * mid > *this)
			r = mid;
		else
			l = mid;
	}
	return l;
}

BigInteger::~BigInteger()
{

}
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
图论2
学习1
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记29
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×