数论笔记（1）

标签：phi frac gcd 数论 笔记 times 互质 mod

1、模运算的性质：

1. 加法：

\[(A+B)\,mod\,C=(A\,mod\,C+B\,mod\,C)\,mod\,C \]

2. 乘法：

\[(A \times B)\,mod\,C=[(A\,mod\,C)\times (B\,mod\,C)]\,mod\,C \]

3. 减法：

\[(A - B)\,mod\,C = [(A\,mod\,C)-(B\,mod\,C)+C]\,mod\,C \]

2、快速幂：

因为\(a^b\)可以看做成\(a^{b_{(2)}}\)（其中的\(x_{(2)}\)表示某数的二进制形式）
所以\(a^b\)可以表达成\(a^{2^i}\)，证明如下：

\[\because a^{b+c} = a^ba^c \]

\[\because b=\sum_{i}^{len(b)}2^i \]

\[\therefore a^{\sum_{i}^{len(b)}2^i}=\prod_i^{len(b)}a^{2^i} \]

根据此性质加以位运算可以快速得出幂的大小。

long long fastfac(long long a,long long b){
	long long ans = 1;
	while(b>0){
		if(b&1)
			ans = ans * a;
		b >>= 1;
		a = a * a;
	}
	return ans;
}

3、欧拉函数φ：

1. 作用：求得小于n的正整数中与n互质的数的数目;
2. 公式：

\[\phi(N)=N\times \prod_{p|N} \frac{p-1}{p} \]

3. 证明：

\[\because n=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times ... \times p_k^{a_k} \]

\[\therefore\phi(n)=\phi(p_1^{a1})\times\phi(p_2^{a2})\times\phi(p_3^{a3})\times...\times\phi(p_m^{am})\{n∈N,p|p\} \]

\[\because \phi(p^k)=p^{k-1}(p-1) \]

\[\therefore\phi(p^k)=p^k(1-\frac{1}{p}) \]

\[\therefore\phi(n)=p_1^{a1}(1-\frac{1}{p_1})\times p_2^{a2}(1-\frac{1}{p_2})\times p_3^{a3}(1-\frac{1}{p_3})\times ... \times p_k^{ak}(1-\frac{1}{p_k}) \]

整理算式，可知：

\[\phi(n)=\prod_{p|n}p^{a}\prod_{p|n}(1-\frac{1}{p}) \]

\[\because n = \prod_{p|n}p^{a} \]

\[\therefore \phi(n)=n*\prod_{p|n}(1-\frac{1}{p}) \]

4. 性质：
   1. 当\(p\)为质数时，\(\phi(p)=p-1\)
   2. 当\(p\)为质数时，\(\phi(p^k)=p^{k-1}(p-1)=p^{k}(1-\frac{1}{p})=p^k(\frac{p-1}{p})\)
   3. 当\(m\)、\(n\)互质时，\(\phi\)为积性函数，即\(\phi(mn)=\phi(m)\times\phi(n)\)
   4. 设\(p\)为质数，若\(p|n\)且\(p^2|n\),则有\(\phi(n)=\phi(\frac{n}{p})\times p\)
   5. 设\(p\)为质数，若\(p|n\)且\(p^2\)不是\(n\)因子，则有\(\phi(n)=\phi(\frac{n}{p})\times(p-1)\)
   6. \(\forall n\in N,n\,=\,\sum_{d|n}\phi(d)\)
   7. \(\forall n > 1,1\sim n\)中与n互质的数的和为\(\frac{n\times \phi(n)}{2}\)
5. 实现：一般用欧拉筛来实现φ

int phi(int num) {
	int fin = sqrt(num);
	int ans = num;
	for (int i = 2; i <= fin; i++) {
		if (num % i == 0) {
			ans /= i;
			ans *= (i - 1);
		}
		while (num % i == 0)
			num /= i;
	}
	if (num > 1) {
		ans /= num;
		ans *= (num - 1);
	}
	return ans;
}

4、\(gcd(a,b)\)和\(lcm(a,b)\)：

1. \(gcd(a,b)\):
   1. 作用：求得\(a\)，\(b\)的所有公因数中最大的一个
   2. 性质：
      1. \(gcd(a,b)=gcd(b,a)\)
      2. \(gcd(a,b)=gcd(-a,b)\)
      3. \(gcd(a,b)=gcd(|a|,|b|)\)
      4. 若有\(d|a\)且\(d|b\)，则\(d|gcd(a,b)\)
      5. \(gcd(a,0)=a\)
      6. \(gcd(a,ka)=a\)
      7. \(gcd(an,bn)=n\, gcd(a,b)\)
      8. \(gcd(a,b)=gcd(a,ka+b)\)
   3. 实现：辗转相除法（欧几里得算法）

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

2. \(lcm(a,b)\):
   1. 作用：求得\(a\)，\(b\)的所有公倍数中最小的一个
   2. 性质：
      1. $gcd(a,b) * lcm(a,b) = a * b $
      2. 若有\(a|m\)且\(b|m\)，则\(lcm(a,b)|m\)
      3. 若\(m,a,b\)是正整数，则\(lcm(ma,mb) = m\times lcm(a,b)\)。
   3. 求\(n\)个数的最小公倍数\((n>2)\)：
   \[lcm(a_1,a_2)=\frac{a_1a_2}{gcd(a1,a2)} \]
   \[lcm(a_1,a_2,a_3) = lcm(lcm(a_1,a_2),a_3) \]

long long lcm(const int a[], int n) {
	long long ans = 1;
	for (int i = 1; i <= n; i++)
		ans = ans * a[i] / gcd(ans, a[i]);
	return ans;
}

5、互质：

1. 定义：\(\forall a,b \in N\),若\(gcd(a,b)=1\)，则称\(a,b\)互质，若\(n\)个整数的最大公因数是1，则称这\(n\)个整数两两互质。
2. 推论：\(a,b\)互质\(\Longleftrightarrow gcd(a,b)=1\)。
3. 性质：
   1. 两个不同的质数一定是互质数
   2. 一个质数，另一个不为它的倍数，这两个数为互质数。
   3. \(1\)既不是质数也不是合数，它和任意一个自然数（除去\(1\)本身外）在一起都是互质的。
   4. 相邻的两个自然数是互质的。
   5. 相邻的两个奇数是互质的。
   6. 较大数是质数的两个数是互质的。

标签：phi,frac,gcd,数论,笔记,times,互质,mod
From： https://www.cnblogs.com/larry76/p/16623683.html