数学 I

本章讨论内容：

• 进制数
• 最大公约数
• 质数

进制数

最为熟知的是十进制，从小到大都在学的。针对逢十进一有深刻认知。而进制数制则是逢几进一则是几进制。

计算机中关键进制：二进制，八进制，十进制，十六进制。其对照关系如下（数数是最初最好理解的办法）。

观察上图：

• 二进制：逢二进一，数码 0 1

• 八进制：逢八进一，数码 0 1 2 3 4 5 6 7

• 十进制：逢十进一，数码 0 1 2 3 4 5 6 7 8 9

• 十六进制：逢十六进一，数码 0 1 2 3 4 5 6 7 8 9 A B C D E F

  
  

因此，涉及到数制问题描述时，数的表示，会有些不同，例如：10 可以是二进制的 2，八进制的 8，十进制的 10，十六进制的 16。

• 二进制的 2：$10_2$, $10_b$, $10_B$
• 八进制的 8：$10_8$, $10_o$, $10_O$
• 十进制的 10：$10_{10}$, $10_d$, $10_D$
• 十六进制的 16：$10_{16}$, $10_h$, $10_H$

显然它们的值是不同的。（可以推广到所有其它进制）

练习

1、写下计算结果的十六进制形式（符号用大写）

$10_2$+$10_8$ = {{ input(1) }}

2、写下十进制的结果

$10_3$ = {{ input(2) }}

进制转换

十进制转二进制：短除法

实际上即将十进制以基数为 2 进行数位分离。

例：分解 $10_{10}$

10 ÷ 2 = 5 ...... 0

5 ÷ 2 = 2 ...... 1

2 ÷ 2 = 1 ...... 0

1 ÷ 2 = 0 ...... 1

取余数倒序即可：$1010_2$ = $10_{10}$

该过程与十进制数位分离（ /10 删个位数，%10 取个位数是一样的，只是现在基数为 2，数位分离基数为 10）

可推广到十进制转任意 f 进制：将基数改为对应进制基数即可。(一般不超过 16 进制)

#include <iostream>
using namespace std;

char i2c[] = "0123456789ABCDEF";
char num[100];
int nl = 0;

int main () {

    int n;
	cin >> n;

	int f = 2; // 目标进制
	// 以 f 为基数的数位分离
	while (n != 0) {
		num[++ nl] = i2c[ n % f ]; // 以字符数组形式存储
		n /= f;
	}

	// 逆序输出十进制 n 在 f 进制下的形式
	for (int i = nl; i >= 1; i --) {
		cout << num[i];
	}
	cout << endl;

    return 0;
}

3、写下结果的二进制形式

$1023_{10}$ = {{ input(3) }}

4、写下结果的二进制形式

$7_{10}$ = {{ input(4) }}

5、写下结果的八进制形式

$19_{10}$ = {{ input(5) }}

6、写下结果的三进制形式

$19_{10}$ = {{ input(6) }}

f 进制转十进制

按权值位展开，乘以权值累加。从个位开始从右往左，第 i 为权值为 $f^{i-1}$

以二进制 $1010_2$ 为例：

第 1 位，值 0，权值 $2^0$

第 2 位，值 1，权值 $2^1$

第 3 位，值 0，权值 $2^2$

第 4 位，值 1，权值 $2^3$

计算式：$1*2^3+0*2^2+1*2^1+0*2^0 = 10$

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

char i2c[] = "0123456789ABCDEF";
int c2i[300];

int main(){

	for (int i = '0'; i <= '9'; i ++) c2i[i] = (i - '0');
	for (int i = 'A'; i <= 'F'; i ++) c2i[i] = (i - 'A') + 10;
	
	string s;
	cin >> s;
	int len = s.size();
	long long ans = 0;    // 累加器
	long long f = 16;     // 目标进制
	long long q = 1;
	for (int i = len - 1; i >= 0; i --) {
		ans += c2i[(int)s[i]] * q;
		q *= f;
	}
	cout << ans << endl;
	
	
	return 0;
}

7、写下结果的十进制形式数

$1111_{2}$ = {{ input(7) }}

8、写下结果的十进制形式数

$F_{16}$ = {{ input(8) }}

9、写下结果的十进制形式数

$1111_{8}$ = {{ input(9) }}

10、写下结果的十进制形式数

$1111_{3}$ = {{ input(10) }}

代码涉及字符串的运用，建议之后学习字符串后，自行完成

最大公约数 Greatest Common Divisor

若 a % b == 0 为真，则有

• a 是 b 的倍数
• b 是 a 的约数(因子)

若 a % c == 0 and b % c == 0 为真，则表示 c 是 a 和 b 的公约数 (公因子)。

若 c 是 a 和 b 的公约数中最大的， 则称 c 是 a 和 b 的最大公约数

从定义出发，代码构建：

#include <iostream>
using namespace std;

int main () {

    int a, b;
	cin >> a >> b;

	int c = 0;
	for (int i = 1; i <= b; i ++) {
		if (a % i == 0 && b % i == 0) {
			c = max(c, i);
		}
	}

	printf("gcd(%d, %d) = %d\n", a, b, c);

    return 0;
}

优化思考：

• 因子必然小于 a 和 b
• 从大到小遍历试探，第一个公约数，必然是最大公约数

#include <iostream>
using namespace std;

int main () {

    int a, b;
	cin >> a >> b;

	int c = 0;
	for (int i = b; i >= 1; i --) {
		if (a % i == 0 && b % i == 0) {
			c = i;
			break;
		}
	}

	printf("gcd(%d, %d) = %d\n", a, b, c);

    return 0;
}

特别的

1）若 gcd(a, b) = 1，表示 a 和 b 是互质关系

2）最小公倍数 (Least Common Multiple)

$$lcm(a, b) = \frac{a*b}{gcd(a, b)}$$

---

质数 Prime

又名素数：一个大于 1 的整数，因子只有 1 和其本身的数。

例如：7 是一个质数，因子只有 1 和 7

例如：9 不是一个素数，因子除了 1 和 9 还有 3

从定义出发，很容易有以下的判断办法

#include <iostream>
using namespace std;

int main () {

    int n;
	cin >> n;

	int cnt = 0; // 针对因子计数
	for (int i = 1; i <= n; i ++) {
		if (n % i == 0) {
			cnt ++;
		}
	}

	if (cnt == 2) {
		cout << "is prime" << endl;
	} else {
		cout << "is not prime" << endl;
	}

    return 0;
}

优化1：考虑到对于一个大于 1 的自然数 n，1 和 n 必然是因子，因此只需要判断 2~n-1 之间不存在第 3 个因子则是质数即可。！！此时，对于 n 的数据范围需要特判

#include <iostream>
using namespace std;

int main () {

    int n;
	cin >> n;

	if (n <= 1) {
		cout << "is not prime" << endl;
		return 0;
	}

	int cnt = 0; // 针对因子计数
	for (int i = 2; i <= n-1; i ++) {
		if (n % i == 0) {
			cnt ++;
		}
	}

	if (cnt == 0) {
		cout << "is prime" << endl;
	} else {
		cout << "is not prime" << endl;
	}

    return 0;
}

优化2：考虑到对于一个大于 1 的自然数 n，因子除了是完全平方数的情况，必然是以 $\sqrt{n}$ 为中线，成双出现，因此只需要判断 2~$\sqrt{n}$ 之间不存在因子则是质数即可。！！此时，对于 n 的数据范围需要特判

#include <iostream>
using namespace std;

int main () {

    int n;
	cin >> n;

	if (n <= 1) {
		cout << "is not prime" << endl;
		return 0;
	}

	int cnt = 0; // 针对因子计数
	for (int i = 2; i <= n / i; i ++) {
		if (n % i == 0) {
			cnt ++;
		}
	}

	if (cnt == 0) {
		cout << "is prime" << endl;
	} else {
		cout << "is not prime" << endl;
	}

    return 0;
}

优化3：2~$\sqrt{n}$ 之间不存在因子, 反向思考，即内部但凡出现一个因子，则不是质数，可以提前结束判断。！！此时，对于 n 的数据范围需要特判

#include <iostream>
using namespace std;

int main () {

    int n;
	cin >> n;

	if (n <= 1) {
		cout << "is not prime" << endl;
		return 0;
	}

	int cnt = 0; // 针对因子计数
	for (int i = 2; i <= n / i; i ++) {
		if (n % i == 0) {
			cnt ++;
			break; // 提前退出计数判断
		}
	}

	if (cnt == 0) {
		cout << "is prime" << endl;
	} else {
		cout << "is not prime" << endl;
	}

    return 0;
}

可尝试用以上三份代码分别判断：1410065413 是否是一个质数，并感受效率