前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

数学

唯一分解定理

n>=2都可以表示为质因数的乘方。
令 n = a1^b1a2^b2$\dots$
a1,b1$\dots$都是质因数，b1,b2$\dots$是对应质因数的数量。

下面是封装类：结果存放在vector m_a, m_n

class CUniqueFactorization
{
public:
	CUniqueFactorization(int iMax) {
		int iMaxSqrt = sqrt(iMax) + 2;
		m_vPrime = CreatePrime(iMaxSqrt);
	}
	void Factorization(int x) {
		m_a.clear();
		m_n.clear();
		for (const auto& iPre : m_vPrime) {
			int cnt = 0;
			while (0 == x % iPre) {
				cnt++;
				x /= iPre;
			}
			if (cnt > 0) {
				m_a.emplace_back(iPre);
				m_n.emplace_back(cnt);
			}
		}
		if (x > 1) {
			m_a.emplace_back(x);
			m_n.emplace_back(1);
		}
	}
	vector<int> m_a, m_n;
	vector<int> CreatePrimeOld(int iMax)
	{
		vector<int> vNo(iMax + 1);
		vector<int> vPrime;
		for (int i = 2; i <= iMax; i++)
		{
			if (!vNo[i])
			{
				vPrime.emplace_back(i);
			}
			for (const auto& n : vPrime)
			{
				if (n * i > iMax)
				{
					break;
				}
				vNo[n * i] = true;
			}
		}
		return vPrime;
	}
	vector<int> CreatePrime(int iMax)
	{
		vector<bool> isPrime(iMax + 1, true);
		vector<int> vPrime;
		for (int i = 2; i <= iMax; i++)
		{
			if (isPrime[i])
			{
				vPrime.emplace_back(i);
			}
			for (const auto& n : vPrime)
			{
				if (n * i > iMax) { break; }
				isPrime[n * i] = false;
				if (0 == i % n) { break; }
			}
		}
		return vPrime;
	}
	vector<int> m_vPrime;
};

调和级数

1+1/2 + 1/3 +1/4 $\cdots$ 1/ n 约等于 logn。
证明过程：
1/3 + 1/4 < (1/2)$\times$ 2 = 1
1/5 + 1/6 + 1/7 + 1/8 < (1/4)$\times$ 4 = 1
1/9+1/10+…1/16 < (1/8)$\times$ 8 = 1
$⋮$
1/2^(m-1)+$\cdots$+ 1/2^m < 1

区间公约数

n个数，那些数对非互质。两两枚举，时间复杂度是O(nn)。
令这些数最大值为m，枚举那些数是x$\in[2,m]的倍数，则时间复杂度是O(nlogn)。
一，相同值如果大于1，非互质。
二，如果同时x>1的倍数，非互质。
转化成并集查找计算连通区域，注意：两个连通区域合并，只需要从2个联通区域任取一点相连。

质数

质数分解

x的质因数中最多有一个大于 x \sqrt x x ​。反证法：如果有两个质因数大于 x \sqrt x x ​，则它们相乘大于 x × x \sqrt x \times \sqrt x x ​×x ​，和所有质因数相乘等于x矛盾。
小于等于x的质因数可以直接枚举。如何寻找大于 x \sqrt x x ​的质因数？
x 如果包括小于等于 x \sqrt x x ​的质因数x1，则x $÷$=x1。直到不包括小于等于 x \sqrt x x ​的质因数。如果此时x>1，则此时的x也是质因数。

for (int i = 0; i < nums.size(); i++) {
			int tmp = nums[i];
			for (auto& iPri : vPrime) {
				if (iPri * iPri > tmp) { break; }
				if (0 == tmp % iPri) { indexs[iPri].emplace_back(i); }
				while ((0 == tmp % iPri)) {
					tmp /= iPri;
				}
			}
			if( tmp > 1){ indexs[tmp].emplace_back(i); }
		}

埃氏筛

如何寻找[1,m]所有质数。从2其，如果i是质数，则将i的x倍（x>1)标记位非质数。时间复杂度：O(nlogn)，logn是调和级数的和。

vector<int> CreatePrime(int iMax)
{
	vector<int> vNo(iMax + 1);
	vector<int> vPrime;
	for (int i = 2; i <= iMax; i++)
	{		
		if (!vNo[i])
		{
			vPrime.emplace_back(i);
		}
		for (const auto& n : vPrime)
		{
			if( n * i > iMax )
			{
				break;
			}
			vNo[n * i] = true;
		}		
	}
	return vPrime;
}

欧拉筛（线性筛）

埃氏筛枚举了所有a$\times$b，其中a是质数，b是任意数。
欧拉筛增加了新条件：a <= b的最小质因数，也就a 是 a$\times$b 的最小质因数。因为任意数的最小质因数都只有一个，故不会重复。故时间复杂度：O(n)
以12为例：
埃氏筛枚举了2次，2$\times$ 6 ，3$\times$ 4。
欧拉筛：只枚举了 2$\times$ 6 。4 枚举完2后，就结束了。

代码

vector<int> CreatePrime(int iMax)
{
	vector<bool> isPrime(iMax + 1,true);
	vector<int> vPrime;
	for (int i = 2; i <= iMax; i++)
	{
		if (isPrime[i])
		{
			vPrime.emplace_back(i);
		}
		for (const auto& n : vPrime)
		{
			if (n * i > iMax){break;}
			isPrime[n * i] = false;
			if (0 == i % n) { break; }
		}
	}
	return vPrime;
}

最大公约数

gcc,vc都有gcd函数，可以直接使用。

辗转相减法

求a,b的最大公约数。如果a,b相等，则a就是公约数。下面只讨论两者不等。
不失一般性，令a > b,其最大公约数为q。a = a1q,b=b1q ，令a - b =（a1-b1)q =c1q= c。则q也是(c,b)的公约数。
我们用反证法来证明c,b没有大于q的公约数。假定c,b有大于q的公约数q1，则a = (b2+c2)q2 ,b = b2q2。a,b也有公约数q2，和a,b的最大公约数是q矛盾。
不断持续此过程，可以保持公约数不变的情况下，让max(a,b)变小。由于a>b，故c >= q。经过有限回合，c一定变成q，b变成q后，a每次也减少q，直到a也变成q。

辗转相除法（欧几里得）求最大公约数

( a , b ) → 不失一般性，令 a > = b ( c = a m o d    b , d = b ) → 不失一般性，令 c > = d ( e = c m o d    d , f = d ) ⋯ (a,b)^{不失一般性，令a >= b}_\rightarrow (c= a \mod b,d= b) ^{不失一般性，令c >= d}_\rightarrow (e=c \mod d,f=d) \cdots (a,b)→不失一般性，令a>=b​(c=amodb,d=b)→不失一般性，令c>=d​(e=cmodd,f=d)⋯
直到最后的两个数一个为0，则公约数是另外一个。比如：e为0，最大公约数就是f。f为0，最大公约数为e。
a,b不断变小，有限次数一定有一个数变为0。
令某两个数的最大公约数为q， $$则这两个数可以表示为q\times a,q\times b则q\times (a\mathrm{mod}b),q\times b的最大公约数为q$$
a%b 为0,也符合数学定义: 0和任何数x的最大公约数是x。

二进制求公约数

求a,b的最大公约数。
一，如果a，b都是偶数，则GCD(a,b) = 2*GCD(a,b)。
二，如果a 是偶数，b是奇数（反之类似）。GCD(a,b)=GCD(a/2,b)。b是奇数，所以他们的公约数不包括2。
三，两者都是奇数。
3.1，两者相等。a就是最大公约数。
3.2，a b不等，不失一般性，令a>b。GCD(a,b) == GCD(a+b,b) == GCD((a+b)/2,b)
由于a,b是不断变小，一定会相等。

菲蜀定理

【数学归纳法 反证法】菲蜀定理

题解2024年11月9整理

余数	难度分
【C++ 前缀和 数论】1590. 使数组和能被 P 整除	2038
【C++数论】2029. 石子游戏 IX	2277

质数判断、分解	难度分
【C++前缀和 数论 贪心】2245. 转角路径的乘积中最多能有几个尾随零	2036
【单调栈】LeetCode:2818操作使得分最大	2396
【状态机dp 状态压缩 分组】1994. 好子集的数目	2464
【分解质因数 差分数组】2584. 分割数组使乘积互质	2519

最大公约数	难度分
【栈 最小公倍数 最大公约数】2197. 替换数组中的非互质数	2057
【最大公约数 排序】2344. 使数组可以被整除的最少删除次数	1640
【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和	2072
【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达	2220
【最大公约数】2862. 完全子集的最大元素和	2291

区间最大公约数：调和级数o(nlogn)	难度分
【最大公约 调和奇数 并集查找】2709. 最大公约数遍历	2171
【调和级数 并集查找】1627. 带阈值的图连通性	2221
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目	2246
【并集查找 最大公约数 调和数】952. 按公因数计算最大组件大小	2272
【数论 最大公约数 调和数】【最大公约数】1819. 序列中不同最大公约数的数目	2539

菲蜀定理	难度分
【菲蜀定理 子序列】1250 检查「好数组」	1983

|唯一分解定理|难度分|

【唯一分解定理 数学】1808好因子的最大数目	2070
【唯一分解定理】【动态规划】【前缀和】1735生成乘积数组的方案数	2499

类似区间公约数	难度分
【动态规划】【前缀和】【分组】2338. 统计理想数组的数目	2615

其它	难度分
【数位dp】【数论】【动态规划】2999. 统计强大整数的数目	2351
【数论 状态机dp】2572. 无平方子集计数	2419
【数论 排序 滑动窗口】1040. 移动石子直到连续 II	2455