算法笔记(三)：数学问题

标签：int len down ++ 算法数学笔记 bign result

最大公约数

辗转相除法

int gcd(int a, int b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

最小公倍数

根据最大公约数得出最小公倍数

步骤：

先求得a与b的最大公约数d
用a * b / d结果就是要求得的最小公倍数，为了防止数据溢出，也可以写为a / d * b

对分数的处理

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

int gcd(int a, int b) {
	if(b == 0) return a;
	else gcd(b, a % b);
}

struct Fraction {
	int up, down;	//分子、分母
}p[3];

//对分数进行处理
Fraction reduction(Fraction result) {
	if(result.down == 0) {	//分子为0 
		result.down = 1;
	}
	if(result.down < 0) {
		result.down = -result.down;
		result.up = -result.up;
	}
	else {
		//约分化简 
		int d = gcd(result.up, result.down);	//最大公约数 
		result.up = result.up / d;
		result.down = result.down / d;
	}
	return result;
}

//分数加法 
Fraction add(Fraction f1, Fraction f2, Fraction result) {
	result.up = f1.up * f2.down + f2.up * f1.down;
	result.down = f1.down * f2.down;
	return reduction(result);
}

//分数乘法
Fraction mult(Fraction f1, Fraction f2,Fraction result) {
	
	result.up = f1.up * f2.up;
	result.down = f1.down * f2.down;
	return reduction(result);
}

//输出
void showResult(Fraction res) {
	res = reduction(res);	//化简
	if(res.down == 1) cout<<res.up<<endl;	//分母为1，输出整数
	else cout<<res.up<<"/"<<res.down<<endl;
} 

int main() {
	p[0].up = 10; 
	p[0].down = 4;
	p[1].up = 7;
	p[1].down = 3;
	showResult(p[0]);
	showResult(p[1]);
	showResult(add(p[0], p[1], p[2]));
	showResult(mult(p[0], p[1], p[2]));
	return 0;
}
//输出
5/2
7/3
29/6
35/6

素数

素数即在2~n-1范围内大于1并且只有1和自身两个约数的数，我们可以缩小范围至2~sqrt(n)

普通方法求素数，时间复杂度是O(n * sqrt(n))，如果数据量超过了10⁵则不行了

#include<bits/stdc++.h>
using namespace std;
//求解100以内的素数

int maxn = 101;
int num = 0;
int res[101];
bool p[101];
 
bool isPrime(int n) {
	for(int i = 2; i <= sqrt(n); i++) {
		if(n % i == 0) return false;
	}
	return true;
}

void Build_Prime() {
	
	for(int i = 2; i < maxn; i++) {
		if(isPrime(i)) {
			res[num++] = i;
//			p[i] = true;
		}
	}
}

int main() {
	Build_Prime();	//建表
	for(int i = 0; i < num; i++) {
		cout<<res[i]<<" ";
	} 
	return 0;
}
//输出
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

埃斯筛法

#include<bits/stdc++.h>
using namespace std;
//求解100以内的素数

const int maxn = 101;
int num = 0;
int res[maxn] = {0};
bool p[101];	//初始化都是0，即false

void Build_Prime() {
	for(int i = 2; i < maxn; i++) {
		if(p[i] == 0) {
			res[num++] = i;	//存素数 
//			p[i] = true;
//			4 6 8 10...
//			6 9 12 15...
//			8 12 16...
			for(int j = i * i; j < maxn; j += i) {
				p[j] = 1;	//存判断条件 
			}
		}
	}
}

int main() {
	Build_Prime();	//建表
	for(int i = 0; i < num; i++) {
		cout<<res[i]<<" ";
	}
	return 0;
}

质因子分解

先获取n以内的素数表，再定义一个结构体

struct factor {
    int x;	//因子
    int cnt;	//该因子个数
};

对sqrt(n)以内的数进行判断能否对n取余，如果能就代表是n的因子，
不断对这个数取余并操作，得到这个因子的个数，
操作到最后得到的n如果是1，则取余完成，如果不是1，则n是一个素数，只有两个因子，一个是1，另一个是它本身

大整数四则运算

对于一个大整数，应该将其存入数组中，再进行操作

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

struct bign {
	int d[1000];
	int len;
	bign() {
		memset(d, 0, sizeof(d));
		len = 0;
	}
};

//将整数转化为数组 
bign change(char ch[] ) {
	bign a;
	a.len = strlen(ch);
	for(int i = 0; i < a.len; i++) {
		a.d[i] = ch[a.len - i - 1] - '0';
	}
	return a;
}
//加法 
bign add(bign a, bign b) {
	bign c;
	int carry = 0;	//进位 
	for(int i = 0; i < a.len || i < b.len; i++) {
		int temp = a.d[i] + b.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	if(carry != 0) {	//当两个数相加到最高位时，可能会进一位 
		c.d[c.len++] = carry;
	}
	return c; 
}

//减法
bign sub(bign a, bign b) {
	bign c;
	for(int i = 0; i < a.len || i < b.len; i++) {
		if(a.d[i] < b.d[i]) {
			a.d[i + 1]--;	//高位借1 
			a.d[i] += 10;
		}
		c.d[c.len++] = a.d[i] - b.d[i];
	}
	while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {	//当最高位是0时去掉 
		c.len--;
	} 
	return c;
} 

//乘法,与学过的乘法不同 
bign mult(bign a, int b) {
	bign c;
	int carry = 0;
	for(int i = 0; i < a.len; i++) {
		int temp = a.d[i] * b + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	while(carry != 0) {	//乘法进位可能不止一位 
		c.d[c.len++] = carry % 10;
		carry /= 10; #
	}
	return c;
}

//除法
int r = 0;
bign divide(bign a, int b) {	//r为余，初始应为0 
	bign c;
	
	c.len = a.len;	//被除数和商长度一一对应，相等 
	for(int i = a.len - 1; i >= 0; i--) {	//从高位开始 
		r = r * 10 + a.d[i];
		if(r < b) c.d[i] = 0;
		else {
			c.d[i] = r / b;
			r = r % b;
		}
	}
	//去掉高位的0 
	while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
		c.len--;
	}
	return c;
}
 
void print(bign a) {
	for(int i = a.len - 1; i >= 0; i--) {
		printf("%d", a.d[i]);
	} 
}

int main() {
	char str1[1000], str2[1000];
	cin>>str1>>str2;
	bign a = change(str1);
	bign b = change(str2);
	print(add(a, b));
	cout<<endl;
	print(sub(a, b));
	cout<<endl;
	print(divide(a, 4));
	cout<<endl;
	cout<<"余数："<<r<<endl; 
	print(mult(a, 11));
	return 0;
}

高精阶乘

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

const int N = 1e4 + 10;
int a[N];
int index = 1;	//表示最大位所在的位置，初始为个位，在a[1]处 

int main() {
	int n;
	cin >> n;
	a[1] = 1;
	for (int i = 1; i <= n; i++) {
		int t = 0;	//进位的数 
		for (int j = 1; j <= index; j++) {
			a[j] = a[j] * i + t;
			t = a[j] / 10;
			a[j] = a[j] % 10;
		}
		while (t > 0) {	//进位 
			a[index + 1] = t % 10;
			t /= 10;
			index++;
		}
	}
	for (int i = index; i >= 1; i--) {
		cout << a[i];
	}
	return 0;
}

高精加法

a + b

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

const int N = 1e4 + 10;
char a[N], b[N];
int p[N], q[N], res[N];

int main() {
	cin >> a >> b;
	int la = strlen(a);
	int lb = strlen(b);
	for (int i = 0; i < la; i++) {
		p[i] = a[la - i - 1] - '0';
	}
	for (int i = 0; i < lb; i++) {
		q[i] = b[lb - i - 1] - '0';
	}
	int len = max(la, lb);
	int t = 0;	//进位的数 
	for (int i = 0; i < len; i++) {
		res[i] = p[i] + q[i] + t;
		t = res[i] / 10;
		res[i] = res[i] % 10;
	}
	if (t == 1) cout << 1;
	for (int i = len - 1; i >= 0; i--) {
		cout << res[i];
	}
	return 0;
}

标签：int,len,down,++,算法,数学,笔记,bign,result
From： https://www.cnblogs.com/RCLiu/p/16882061.html