FXJFXJ
0%

发表于 分类于
本文字数： 352 阅读时长 ≈ 1 分钟

欧拉函数 \((Euler's totient function)\) 内容：即 \(\varphi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。

性质：

  • 欧拉函数是积性函数。如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)。

  • \(n = \sum_{d \mid n}{\varphi(d)}\)。

  • 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。 （根据定义可知）

  • 由唯一分解定理，设 \(n = \prod_{i=1}^{s}p_i^{k_i}\)，其中\(p_i\) 是质数，有 \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\)。

实现：

阅读全文 »

发表于 更新于 分类于
本文字数： 503 阅读时长 ≈ 2 分钟

1 定义

如果一个线性同余方程 \(ax \equiv 1 \pmod b\)，则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\)。 ## 2 费马小定理： \(x \equiv a^{b-2} \pmod b\)。\(p\) 为质数才成立

3 [[拓展欧几里得]]：

1
2
3
4
5
6
7
8
9
10
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y;
    Exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}

4 线性递推求法：

阅读全文 »

发表于 更新于 分类于
本文字数： 419 阅读时长 ≈ 2 分钟

本质上是用链表实现的邻接表，核心代码如下： 

1
2
3
4
5
6
7
8
9
10
11
int cnt=1;
void add(int u, int v, int w)//链式前向星存图
{
	a[cnt] = {v, w, head[u]};
    //a[cnt].w = w;//这三行与上面一行等价
    //a[cnt].v = v;
    //a[cnt].next = head[u];
    head[u] = cnt++;
}
for (int i = head[u]; i; i = a[i].next)//遍历
{}
\(\cup\) 
1
2
3
4
5
6
7
8
9
10
11
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  // 当前边的后继
  head[u] = cnt;         // 起点 u 的第一条边
  to[cnt] = v;           // 当前边的终点
}

// 遍历 u 的出边
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
  int v = to[i];
}
示例代码： 
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
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> head, nxt, to;

void add(int u, int v) {
  nxt.push_back(head[u]);
  head[u] = to.size();
  to.push_back(v);
}

bool find_edge(int u, int v) {
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    if (to[i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  head.resize(n + 1, -1);

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
  }

  return 0;
}
阅读全文 »

发表于 更新于 分类于
本文字数： 579 阅读时长 ≈ 2 分钟

1 如何实现离散化？

![[../../../images/Z-attachment/Pasted image 20231126151937.png]] ## 2 解析 我们可以发现，最后归位后的数组就对应的是 \(Rank\) 的值，因此这道题就是去求出最后的数组。注意本题要去重，因此在离散化之前排序之后要去一遍重。

怎么用代码实现？ 这道题要有两个数组，一个原数组，设为 \(a\)。一个离散化归位数组，设为 \(d\)。输入时要将原数组同步到离散化数组上。

第一步没啥好说的，对原数组排序。

第二步之前要进行去重，我们可以用 STL 中的一个神奇的函数：\(Unique\)，STL 好闪，拜谢 STL，使用方法跟 \(Sort\) 函数一样，只不过没有第三个参数。

阅读全文 »

发表于 更新于 分类于
本文字数： 392 阅读时长 ≈ 1 分钟

1 模板

注意开 long long 

1
2
3
4
5
6
7
8
9
10
11
12
int qpow(int x, int y)
{
    int ans = 1;
    while (y)
    {
        if (y % 2)
            ans = (ans * x) % p;
        x = (x * x) % p;
        y /= 2;
    }
    return ans;
}

2 矩阵计算

阅读全文 »

发表于 分类于
本文字数： 660 阅读时长 ≈ 2 分钟

二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

模板
模板 1：
1
2
3
4
5
6
while (l < r)
{
	int mid = l + r >> 1;	//(l+r)/2
	if (check(mid))  r = mid;    // check()判断mid是否满足性质
	else l = mid + 1;
}
模板 2：
阅读全文 »

发表于 更新于 分类于
本文字数： 230 阅读时长 ≈ 1 分钟

1 模板

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
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[10010];
// int find(int x)
// {
//     while (x != f[x])
//         x = f[x] = f[f[x]];
//     return x;
// }
//路径压缩
int find(int x)
{
    if(x==f[x])
        return x;
    return f[x] = find(f[x]);
}
//int find(int x)//或者这样写
//{
//   return x == f[x] ? x : (f[x] = find(f[x]));
//}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    while (m--)
    {
        int op, x, y;
        cin >> op >> x >> y;
        int a = find(x), b = find(y);
        if (op == 1)
        {
            f[a] = b;
        }
        else
        {
            if(a==b)
                cout << "Y" << endl;
            else
                cout << "N" << endl;
        }
    }
}

2 练习

2.1 P1551 亲戚 - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
int n, m, p;
int f[10010];
int find(int x)
{
    return x == f[x] ? x : (f[x] = find(f[x]));
}
int main()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        int a = find(x), b = find(y);
        f[a] = b;
    }
    while (p--)
    {
        int x, y;
        cin >> x >> y;
        int a = find(x), b = find(y);
        if (a == b)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}
阅读全文 »

发表于
本文字数： 7 阅读时长 ≈ 1 分钟 
1
2
list
from "source/_posts/Demo/ACMWeb"