【数轮】数论、质数、最大公约数、菲蜀定理

数学

唯一分解定理

n>=2都可以表示为质因数的乘方。

令 n = a1b1a2b2 … \dots …

a1,b1 … \dots …都是质因数，b1,b2 … \dots …是对应质因数的数量。

调和级数

1+1/2 + 1/3 +1/4 ⋯ \cdots ⋯ 1/ n 约等于 logn。

证明过程：

1/3 + 1/4

1/5 + 1/6 + 1/7 + 1/8

1/9+1/10+…1/16

⋮ \vdots ⋮

1/2^(m-1)+ ⋯ \cdots ⋯+ 1/2m

区间公约数

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 ÷ \div ÷=x1。直到不包括小于等于 x \sqrt x x ​的质因数。如果此时x>1，则此时的x也是质因数。

for (int i = 0; i  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 CreatePrime(int iMax)
{
	vector vNo(iMax + 1);
	vector vPrime;
	for (int i = 2; 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 vector 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; } h2最大公约数/h2 pgcc,vc都有gcd函数，可以直接使用。/p h3辗转相减法/h3 p求a,b的最大公约数。如果a,b相等，则a就是公约数。下面只讨论两者不等。/pp不失一般性，令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 × a , q × b 则 q × ( a m o d    b ) , q × b 的最大公约数为 q 则这两个数可以表示为q \times a,q \times b 则 q \times (a \mod b) , q \times b 的最大公约数为q 则这两个数可以表示为q×a,q×b则q×(amodb),q×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是不断变小，一定会相等。

菲蜀定理

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

题解