1
//链式前向星的标准实现方式
2
void add(int x, int y, int z){ //点x到点y的一条权值为z的一条边
3
  ver[++tot] = y;  //ver表示新边的中点，tot记录第i条边(当前已添加边的总数)
4
  edge[tot] = z;   //edge记录边权值
5
  nxt[tot] = head[x]; //将新边的的“下一条边”指向原来x的最后一条边
6
  head[x] = tot;   //更新 head[x]，使其指向最新加入的这条边
7
}

1
bool isprime(int n){
2
    if(n < 2) return 0;
3
    for(int i = 2; i <= sqrt(n); i++)
4
        if(n % i == 0) return 0;
5
    return 1;
6
}

1
bool v[];
2
void find_primes(int n;){
3
    memset(v, 0, sizeof(v));
4
    for(int i = 2; i <= n; i++){
5
        if(v[i]) continue;
6
        cout << i << " ";
7
        for(j = 1; j <= n/i; j++) v[i*j] = 1;
8
    }
9
}

1
void divide(int n){
2
    int m = 0;
3
    for(int i = 2; i <= sqrt(n); i++){
4
        if(n % i == 0){  //i 是质数
5
            prime[++m] = i，c[m] = 0;
6
            while(n % i == 0) n /= i, c[i]++;  //除掉所有的i;
7
        }
8
        if(n > 1)
9
            p[++m] = n, c[m] = 1;
10
        for(int i = 1; i <= m; i++)
11
            cout << p[i] << "^" << c[i] << "*";
12
    }
13
}

1
int gcd(int a, int b){
2
    return b ? gcd(b, a % b) : a;
3
}
4
int lcd(int a, int b){
5
    return a * b / gcd(a, b);
6
}

1
int phi(int n){
2
    int ans = n;
3
    for(int i = 1; i <= sqrt(n); i++){
4
        if(n % i == 0){
5
            ans = ans * (i - 1) / i;
6
            while(n % i == 0) n /= i;
7
        }
8
        if(n > 1) ans = ans * (n - 1) / n;
9
    }
10
    return ans;
11
}

1
sort(p.begin(), p.end(), cmp); //无cmp时，sort默认从大到小
2
sort(a, a+n);
3
sort(a+1, a+n+1); //对比，注意用下标排序

1
struct node{
2
    int score;
3
    int id;
4
  string name;
5
} stu[10000];
6
bool cmp(node a, node b){
7
  if(a.score != b.score) return a.score > b.score;
8
    else return a.name > b.name;
9
}

1
//C语言中默认无重载运算符，不可以直接用<>=比较，使用strcmp函数
2
struct node{
3
    int score;
4
    int id;
5
  char name[100];
6
} stu[10000];
7
bool cmp(node a, node b){
8
  if(a.score != b.score) return a.score > b.score;
9
    else return strcmp(a.name, b.name);
10
}

1
int f[1000];  //存每个元素的爸爸
2
int find(int x){
3
  if(f[x] == x) return x; //自己是自己的爸爸
4
  return f[x] = find(f[x]); //自己有爸爸，那就找找爸爸的爸爸是谁？找到的也是自己的爸爸
5
}

1
lower_bound(first, last, val) // 指向第一个 >= 4 的位置
2
upper_bound(first, last, val) // 指向第一个 > 4 的位置

1
string s = "abc";//s = "123";
2

3
sort(s.begin(), s.end()); // 确保从最小字典序开始
4
do{
5
    cout << s << endl;
6
} while(next_permutation(s.begin(), s.end()));
7
// 输出: abc, acb, bac, bca, cab, cba

1
long long fact[N];    // 阶乘数组: fact[i] = i! % MOD
2
//fact[i] = (fact[i - 1] * i) % MOD;
3

4
long long inv_fact[N];  // 阶乘逆元数组: inv_fact[i] = (i!)^(MOD-2)% MOD
5
for(int i = 1; i <= max_n; ++i)
6
  inv_fact[max_n] = quick_pow(fact[max_n], MOD - 2, MOD); // 利用费马小定理计算最大阶乘的逆元
7

8
for(int i = max_n - 1; i >= 0; --i)
9
  inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD; // 递推计算其他阶乘的逆元: (i-1)!^-1 = i!^-1 * i