集合

子集遍历

质数

定义

质数与合数的定义：质数与合数是针对所有大于 1的自然数来定义的，也就是说所有小于等于 1的数字都不属于质数和合数的范围。 在大于 1的整数中，如果只包含 1和本身两个约数，就被称为质数（素数）；反之为合数。

线性判断质数

枚举2~n-1的所有数，然后判断是否整除n。 代码：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n-1; i++) {
		if (n%i == 0) return 0;
	}
	return 1;
}

分解质因数

#include<bits/stdc++.h>
using namespace std;
int main() {
    int s;
    cout << "请输入一个正整数: ";
    cin >> s;

    cout << s << " 分解质因数为: ";
    for (int i = 2; i <= s; i++) {
        while (s % i == 0) {
            cout << i;
            s /= i;
            if (s != 1) cout << " * ";
        }
    }
    cout << endl;
    return 0;
  //输出：请输入一个正整数: 12
  //分解质因数为: 2 * 2 * 3
}

基本原理

质数的定义：质数是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。例如 2、3、5、7、11 等都是质数。在分解质因数过程中，这些质数是基本的组成元素。

合数的可分解性：任何一个合数都可以唯一地分解成若干个质数的乘积，这被称为算术基本定理。比如，合数 6 可以分解为 2×3，8 可以分解为 2×2×2 。这保证了分解质因数算法的可行性和结果的唯一性。

在需要多次判断质数的场景，比如统计某个区间内的所有质数时，我们想要让程序运行的快一些时，就需要质数筛了。 质数筛有朴素筛，埃氏筛，欧拉筛等等。 但是我们最常用的是埃氏筛（以下是埃氏筛的代码）

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;  // 质数存到数组中
			for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉质数的倍数
		}
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。

定义：埃氏筛法是一种在给定上界n的情况下，能够找出从2到n之间所有素数的算法。

原理：素数是只能被1和自身整除的整数。所以，通过从2开始，依次标记每个素数的倍数为合数，最终未被标记的数即为素数。

约数

定义

如果整数a除以整数b(b!=0)的商正好是整数且没有余数，我们就说b是a的约数。例如，6÷2=3，2和3都是6的约数。1 是所有非零整数的约数，因为任何非零整数除以1都能整除。同时，一个数本身也是它自己的约数，比如6也是6的约数。

性质

一个数的约数是有限的。例如18的约数有1、2、3、6、9、18，总共6个。如果a是b的约数，b是c的约数，那么a也是c的约数。比如2是4的约数，4是8的约数，那么2也是8的约数。两个数的公约数是它们公共的约数。例如12和18，12的约数有1、2、3、4、6、12，18的约数有1、2、3、6、9、18，它们的公约数有1、2、3、6 ，其中最大公约数是6。求最大公约数可以使用辗转相除法,更相减损法等方法。

线性枚举约数

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n; i++) {
		if (n%i == 0) res[++cnt] = i;
	}
}

快速幂

幂是一个数自乘若干次的形式，乘方的结果叫做幂。比如n的m次幂意为m个n相乘，写做$n^m$,其中𝑛称为底数，𝑚称为指数。 代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

/**
快速幂模板题
a 底数，b 指数
 */
ll qmi(ll a, ll b, ll p) {
    ll ans = 1;           // 初始化结果为1
    while (b) {           // 循环直到指数b变成0
        if (b & 1)        // 判断当前b的二进制最低位是否为1
            ans = ans * a % p;  // 如果为1，将当前a累计乘到结果中并取模
        a = a * a % p;    // 将a平方并取模，以便下一位的计算
        b >>= 1;          // 将b右移一位，相当于去掉二进制最低位
    }
    return ans;           // 返回最终结果
}

int main() 
{
    ll a, b, p;
    cin >> a >> b >> p;   // 输入底数a、指数b和p
    cout << qmi(a, b, p); // 调用快速幂取模函数并输出结果
    return 0;
}

龟速乘

龟速乘的核心思想是将乘法转换为加法，通过二进制分解和累加的方式逐步计算结果，从而避免直接相乘导致的溢出。 其实就是把快速幂的乘法改成加法。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;                        
ll qmi(ll a,ll b,ll p){
	ll ans = 0;
	while(b){
		if (b & 1) ans = (ans + a) % p;
        a = a * 2 % p;
        b >>= 1;

	}
	return ans;
}
int main()
{
  	ll a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p);
    return 0;

	return 0;
}