数学

唯一分解定理

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
• 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

调和级数

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的质因数中最多有一个大于$\sqrt{x}$。反证法：如果有两个质因数大于$\sqrt{x}$，则它们相乘大于 $\sqrt{x}\times \sqrt{x}$，和所有质因数相乘等于x矛盾。
小于等于x的质因数可以直接枚举。如何寻找大于$\sqrt{x}$的质因数？
x 如果包括小于等于$\sqrt{x}$的质因数x1，则x $÷$=x1。直到不包括小于等于$\sqrt{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
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

埃氏筛

如何寻找[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;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21

欧拉筛（线性筛）

埃氏筛枚举了所有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;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

最大公约数

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{)}_{\to }^{不失一般性，令a>=b}(c=a\mathrm{mod}b,d=b{)}_{\to }^{不失一般性，令c>=d}(e=c\mathrm{mod}d,f=d)\cdots$$
直到最后的两个数一个为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是不断变小，一定会相等。

菲蜀定理

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

题解