2000字范文,分享全网优秀范文,学习好帮手!
2000字范文 > 保研机试——2数学问题(简单数学 最大公约/最小公倍 分数运算 素数 质因子分解

保研机试——2数学问题(简单数学 最大公约/最小公倍 分数运算 素数 质因子分解

时间:2019-08-05 22:06:32

相关推荐

保研机试——2数学问题(简单数学 最大公约/最小公倍 分数运算 素数 质因子分解

1 简单数学2 最大公约/最小公倍3 分数运算4 素数5 快速幂5 高精度问题6 常见数学公式总结7 规律神器OEIS

1 简单数学

(1)同余模定理:所谓的同余,顾名思义,就是许多的数被一个数 d 去除,有相同的余数d数学上的称谓为。如 a = 6, b = 1, d = 5, 则我们说 a 和 b 是模 d 同余的。因为他们都有相同的余数 1 。

数学上的记法为: (是 ≡ (mod d))

a ≡ b(mod d)

可以看出当 n < d 的时候,所有的 n 都对 d 同商,比如时钟上的小时数,都小于 12,所以小时数都是模 12 的同余. 对于同余有三种说法都是等价的,分别为:

(1) a 和 b 是模 d 同余的. (2) 存在某个整数 n ,使得 a = b + nd . (3) d 整除 a - b .

定律:同余公式也有许多我们常见的定律,比如相等律,结合律,交换律,传递律….如下面的表示:

1) a≡a(mod d) 2) a≡b(mod d)→b≡a(mod d) 3) (a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则

4) a+b≡x+m (mod d) 5) a-b≡x-m(mod d) 6) a*b≡x*m(mod d )

应用:加减乘的mod可拆!!同余模定理的运算不适用于除法除法等价于乘倒数(逆元),对于除法取模的运算我们一般使用逆元来解决问题

(a+b)%c=(a%c+b%c)%c;(a-b)%c=(a%c-b%c)%c; (a*b)%c=(a%c*b%c)%c;

如当n^5却超过long long的范围,只要我们对答案%3,这时候我们就可以运用同余模定理,分解取摸

大数取模:这里的大数指无法用long long保存的数,每位被存在string s[i]中,对其求余联想到进制转换时的方法,举例如下,设大数 m=1234, 模 n 就等于

1234%n=1000%n + 200%n + 30%n + 4%n= ((((1*10)%n + 2%n)%n *10 %n + 3%n)% n *10 %n + 4%n)%n

for(i = 0; s[i] != '\0'; i++) m = ((m * 10) % n + (s[i] - '0') % n) % n;

(2)数位拆解:十进制数x,不断重复将x对10求模,除以10,就可以得到数字x各个数位上的数字。

//拆分while (x){//得到当前整数x、个位数subsub = x% 10;//切割这一整形x/= 10;//输出cout << sub;}

(3)进制转化:将M进制的数X转换为N进制的数并输出。

输入的第一行包括两个整数:M和N(2 ≤ M , N ≤ 36)

下面的一行输入一个数X,X是M进制的数,现在要求你将M进制的数X转换成N进制的数并输出。

#include<iostream>#include<cstdlib>#include<string>#include<vector>#include<algorithm>#include<stack>using namespace std;/*题目描述: 从M进制转换到N进制*/string divide(string str, int x,int &reminder){//字符串除法,reminder是余数reminder = 0;for(int i = 0;i<(int)str.size();i++){int current = (str[i]-'0') + reminder*10;str[i] = (current/x)+'0';reminder = (current%x);}int pos = 0;while(str[pos] == '0') pos++;return str.substr(pos);}string mutiply(string str, int x){//字符串乘法,结果为10进制字符串int carry = 0;for(int i = str.size()-1;i>=0; i--){int current = x*(str[i]-'0')+carry;str[i] = (current%10)+'0';carry = current/10;}if(carry) str.insert(0,1,carry+'0');return str;}string add(string str, int x){//字符串加法,结果为10进制字符串int carry = x;for(int i = str.size()-1; i>=0; i--){int current = (str[i]-'0')+carry;str[i] = (current%10)+'0';carry = (current/10);if(!carry) break;}if(carry) str.insert(0,1,carry+'0');return str;}int ToInt(char c){//进制位值转换为int值if('0'<= c && c <= '9') return c-'0';if('A'<= c && c <= 'Z') return c-'A'+10;} char ToChar(int x){//int值转换为进制位值if(x<10) return x+'0';else return (x-10)+'A';}int main(){int M,N;cin>>M>>N;string str;cin>>str;string decimal = "0";stack<char> answer;for(int i = 0;i<str.size();i++){//转换为10进制decimal = mutiply(decimal,M);decimal = add(decimal,ToInt(str[i]));}while(decimal != ""){//转换为N进制int bit;decimal = divide(decimal,N,bit); //bit作为余数被传回answer.push(ToChar(bit));}while(!answer.empty()){cout<<answer.top();answer.pop();}cout<<endl;return 0;}

2 最大公约/最小公倍

(1)最大公约数gcd:使用欧几里得算法

若a,b全为零,则他们的最大公约数不存在;若a,b其中之一为零,则最大公约数为a,b中的非零数;若都不为零,则可以使新a=b, b=a%b递归重复该过程,直到其中一个为零。

# include<iostream>using namespace std;int gcd(int a,int b){if(b==0) return a;else return gcd(b,a%b);}

实际上我们也不需要记忆,c++的#include<algorithm>中已经实现了该函数__gcd(x,y)

判断x和y互质gcd(x,y)==1

分数化简x / y = (x/gcd(x,y)) / (y/gcd(x,y))

(2)最小公倍数lcmlcm(a,b) = (a*b) / gcd(a,b)。所以求得最大公约数即求得最小公倍数。

#define __lcm(x,y) x*y/__gcd(x,y)cout<<__lcm(x,y);

3 分数运算

对分数求加减乘除,以及化简

#include<iostream>#include<math.h>using namespace std;//分数结构体struct Fraction{long up,down;};//求分子分母的最大公约数int gcb(int a,int b){if(b==0)return a;elsereturn gcb(b,a%b);}//化简Fraction reduction(Fraction &result){if(result.down < 0) //分母为负{result.down = -result.down;result.up = - result.up;}else if(result.up == 0) //分母为0result.down = 1;else{int x = gcb(abs(result.up),abs(result.down)); //分子分母同时除最大公约数result.up /= x;result.down /= x;}return result;}//加法Fraction Add(Fraction a,Fraction b){Fraction c;c.up = a.up * b.down + a.down * b.up;c.down = a.down * b.down;return reduction(c);}//减法Fraction minu(Fraction a,Fraction b){Fraction c;c.up = a.up * b.down - a.down * b.up;c.down = a.down * b.down;return reduction(c);}//乘法Fraction multi(Fraction a,Fraction b){Fraction c;c.up = a.up * b.up;c.down = a.down * b.down;return reduction(c);}//除法Fraction divide(Fraction a,Fraction b){Fraction c;c.up = a.up * b.down;c.down = a.down * b.up;return reduction(c);}void showresult(Fraction result){if(result.down == 1)cout<<result.up<<endl;else if(abs(result.up)>abs(result.down))cout<<result.up /result.down <<" "<<abs(result.up % result.down)<<"/"<<result.down<<endl;elsecout<<result.up<<"/"<<result.down<<endl;}int main(){Fraction f1,f2;while(cin>>f1.up>>f1.down>>f2.up>>f2.down){showresult(Add(f1,f2));showresult(minu(f1,f2));showresult(multi(f1,f2));showresult(divide(f1,f2));}return 0;}

4 素数

素数/质数,是指除了1和本身之外,不能被其他数整除的数。

合数/非素数:是指除了1和本身之外,能被其他数整除的数。

(1)判断素数

int x,flag=0;cin>>x;if(x==1){cout<<"no";continue;}rep(i,2,sqrt(x)+1){if(x%i==0){flag=1;break;}}if(flag==0)cout<<"yes"<<endl;else cout<<"no"<<endl;

筛选[1,n]区间内的素数,逐个用上面的方法复杂度是 O ( n ∗ s q r t ( n ) ) O(n*sqrt(n)) O(n∗sqrt(n)),我们需要找到一种线性复杂度的筛法 O ( n ) O(n) O(n)

(2)筛法求素数筛法,若一个数不是素数,则必存在一个小于它的素数为其因数。换一个角度来讲,在获得一个素数时,即将它的所有倍数均标记成非素数这样当我们遍历到一个数时,它没有被任何小于它的素数标记为非素数,那么就确定其为素数。(思路就是标记倍数为非素数)

例如:筛选[1,30]的素数

从1开始的、某一范围内的正整数集合从小到大顺序排列,1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。如有:

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其中,1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:3 5 7 9 11 13 15 17 19 21 23 25 27 29剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:2 3 5 7 11 13 17 19 23 29

bool mark[10001];//标记(true表示非素数,即合数)vector<int> prime; //保存素数int main(){int n; cin>>n;for (int i=2; i<n; i++){//求[1,n]内的素数if (mark[i] == true) continue;// 跳过已标记为合数的数prime.push_back(i); // 保存素数ifor (int j=i+i; j<n; j+=i)// 标记 素数i的倍数 为 非素数mark[j] = true;}for(auto e:prime)cout<<e<<' ';return 0;}

(3)素(质)因子分解:即分解整数x素数p i p_i pi​ 和 对应的指数e i e_i ei​。

x = p 1 e 1 + p 2 e 2 + . . . . . . + p n e n x = p_1^{e_1}+ p_2^{e_2} +......+p_n^{e_n} x=p1e1​​+p2e2​​+......+pnen​​

step1:首先筛选出小于sqrt(x)的所有素数,然后依次遍历小于x的素数,判断其是否为x的因数。step2:确定某素数为x的因数,则通过试除确定其对应的幂指数

例如对120进行分解,先求[1,120]的所有素数,从小到达,用素数试除120,找到一个可以整除的素数,一直除,直到不能整除,再找更大可整除的素数,直到120被除到1。

120/2 = 6060/2 = 3030/2 = 1515/3 = 55/5 = 1

得到120 = 2*2*2*3*5

//此处省略求[1,sqrt(x)]区间的素数int ansPrime[30];//按顺序保存分解出的素因数piint ansSize=0;//分解出素因数的个数;int ansNum[30];//保存分解出的素因数对应的幂指数eifor(int i=0;i<primeSize;i++){if(x%prime[i]==0){ansPrime[ansSize]=prime[i];ansNum[ansSize]=0;while(x%prime[i]==0){ansNum[ansSIze]++;x/=prime[i];}ansSize++;if(x==1) break;}}

5 快速幂

pow函数求 a b a^{b} ab ,就是把a连乘b次,这样一来时间复杂度是 O ( n ) O(n) O(n), 但快速幂能做到 O ( l o g n ) O(logn) O(logn)的复杂度。

快速幂将次幂b转化为二进制数,如求 a 11 a^{11} a11时,即 1 1 ( 10 ) = 2 ( 10 ) 0 + 2 ( 10 ) 1 + 2 ( 10 ) 3 = 101 1 ( 2 ) 11_{(10)}= 2^0_{(10)}+2^1_{(10)}+2^3_{(10)} =1011_{(2)} 11(10)​=2(10)0​+2(10)1​+2(10)3​=1011(2)​,所以 a 11 = a 2 0 + 2 1 + 2 3 = a 2 0 ∗ a 2 1 ∗ a 2 3 a^{11}=a^{2^0+2^1+2^3}=a^{2^0}*a^{2^1}*a^{2^3} a11=a20+21+23=a20∗a21∗a23,这样一来只需要计算 a 2 0 , a 2 1 , a 2 3 a^{2^0},a^{2^1} ,a^{2^3} a20,a21,a23,并把它们乘起来。实现了11次运算变3次。

对于二进制的位运算,我们需要用到"&“与”>>"运算符

#define LL long longLL quickPow(LL a,LL b){// 求a^bLL res=1; // res存放a^b结果while(b>0){// b>0时不断右移,取二进制最低位if(b&1) res=res*a;//当前二进制b最低位=1时(b%2=1),结果+=结果乘ab>>=1; //二进制b右移一位(十进制b除2)a*=a;//a次方加1(每次b右移一位,a的次方加1)}return res;}

其中“b & 1”指取b的二进制数的最末位,如11的二进制数为1011,第一次循环,取的是最右边的“1” ,以此类推。

而“b >>= 1”等效于b = b >> 1,即右移1位,删去最低位。

变形题目: x n % m x^n \% m xn%m,其中x很大,用大数模拟很麻烦,可以用同余模定理,保证res在int范围内

5 高精度问题

大数的加减乘除,常见的int(10位)和long long( 位)表示10进制整数时 位数不够,需要用数组/string模拟大数,并构造它的运算法则。本质都是模拟逐位运算,进位借位的过程

为方便进位,约定倒着表示结果从个位进行运算,计算完结果反转,如计算大数加法988+99时,诸位计算完倒着的结果是7801,反转为1087.

大数加法a+b:ab都是大数,保证a为最长的数,将b前面补0和a长度相等,for从个位逐位相加,加进位carry,计算下一位的进位carry,计算结束,结束时进位carry不=0,结果最前面插入一位进位值。(因为string在前面插入方便,这里并没有使用上述的结果反转实现,而是直接开一个固定长度的结果,倒着算,不够进位时才插入)仅使用正数

#include<bits/stdc++.h>using namespace std;#define rep(i,s,e) for(int i=s;i<e;i++)#define per(i,s,e) for(int i=s;i>e;i--)string Add(string a, string b){if(a.size()<b.size()) swap(a,b); //使a一直为位数较长的字符串 reverse(a.begin(),a.end()),reverse(b.begin(),b.end()); //反转字符串!!方便从个位开始运算b.insert(b.end(),a.size()-b.size(),'0'); //较短的字符串前面补零方便计算 string res(a.size(),0); //初步设置result长度为较长字符长度 int carry=0,tmp;//carry进位//逐位计算for(int i=0;i<a.size();i++){tmp = (a[i]-'0') + (b[i]-'0') + carry;if(tmp > 9) carry=1;else carry=0;res[i] = tmp%10 + '0';}if(carry==1) res+='1'; //若结束时,进位不为0,还要在结果前面补上进位 reverse(res.begin(),res.end());return res;}int main() {string a, b; while (cin >> a >> b) cout << Add(a, b) << endl; return 0; }

大数减法a-b:ab都是大数,保证A大于等于B,逆序反转字符串,从个位开始计算res[i] = A[i] - B[i] - carry,carry=0,如果不够减则借位res[i] = A[i] - B[i] - carry +10,carry=1.

string Sub(string a, string b){int flag=0;if(a.size()<b.size() || (a.size()==b.size() && a<b )) {swap(a,b); flag=1;}reverse(a.begin(),a.end()),reverse(b.begin(),b.end());b.insert(b.end(),a.size()-b.size(),'0');string res(a.size(),0); int carry=0,tmp;//carry接位//逐位计算for(int i=0;i<a.size();i++){tmp = (a[i]-'0') - (b[i]-'0') - carry;if(tmp <0) carry=1;else carry=0;res[i] =(tmp + 10*carry) + '0';}//去除末尾连续的0 while(res.back()=='0'&&res.size()>1)res.pop_back();if(flag) res+='-'; //flag判断复数reverse(res.begin(),res.end());return res;}

大数乘法a*b: a是大数,b位int型小数,逆序a串从低位开始算,进位可能不止一位数

string Mul(string a, int b){//a是大数,b是小数 reverse(a.begin(),a.end()); string res(a.size(),0); int carry=0,tmp;//carry进位// 54321 * 99for(int i=0;i<a.size();i++){tmp = (a[i]-'0') * b + carry;res[i] =(tmp)%10 + '0';if(tmp >9) carry=tmp/10;else carry=0;}while(carry) {//剩下的进位可能不止一位数res+=carry%10+'0';carry/=10;}reverse(res.begin(),res.end());return res;}

大数除法a/b: a是大数,b位int型小数,不再逆序A串,顺序求余数r。

string div(string a, int b){//a是大数,b是小数 string res; int r=0,tmp;//r余数 //1212/6for(int i=0;i<a.size();i++){tmp = (a[i]-'0') + r*10;r = tmp%b;res += tmp/b + '0';}//去除末尾连续的0reverse(res.begin(),res.end());while(res.back()=='0'&&res.size()>1)res.pop_back();reverse(res.begin(),res.end());cout<<res<<endl<<r;return res;}

6 常见数学公式总结

错排公式

递推公式为:D(n) = (n - 1) * [D(n - 1) + D(n - 2)]

问题描述: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?

海伦公式

S = sqrt(p * (p - a) * (p - b) * (p - c))

公式描述:公式中a,b,c分别为三角形三边长,p为半周长,S为三角形的面积。

组合数公式

c(n,m) = p(n,m)/m! = n!/(n-m)!*m!

公式描述:组合数公式是指从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合。

两点之间的距离公式

|AB|=sqrt( (x1-x2)^2 + (y1-y2)^2 )

公式描述:公式中(x1,y1),(x2,y2)分别为A、B两个点的坐标。

扇形面积

S=1/2×弧长×半径S扇=(n/360)πR²

卡特兰数

卡特兰数的应用实质上都是递归等式的应用

令h(0)=1,h(1)=1,catalan 数满足递归式:

h(n)=h(0)*h(n-1) + h(1)*h(n-2) ......+h(n-1)*h(0)(其中n>=2)

另类递推公式:h(n)=h(n-1)*h(4*n-2)/(n+!)

该递推关系的解为:h(n)=C(2n,n)/(n+1)(n=1,2,3,…)

前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

所有的奇卡塔兰数Cn都满足n = 2^k-1、所有其他的卡塔兰数都是偶数。

应用

1、12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

2、括号化问题。矩阵链乘: P=A1×A2×A3×……×An,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?

3、将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数?

4、出栈次序问题。一个栈(无穷大)的进栈序列为1、2、3、…、n,有多少个不同的出栈序列?

5、通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。

6、所有在n*n格点中不越过对角线的单调路径的个数。

7、有n+1个叶子的二叉树的个数。

更多的变化不胜枚举,遇到这类规律题建议使用下一节的OEIS来解决问题。

7 规律神器OEIS

针对规律题只要你输入前几项,OEIS就可以给你找出规律来,并且自动给你推出公式。所以对于找规律的题目,你只需要手动计算出前几项的值,或者暴力打表求出前几项的值,然后输入OEIS,他就可以告诉你公式是什么。

保研机试——2数学问题(简单数学 最大公约/最小公倍 分数运算 素数 质因子分解 快速幂 高精度问题 常见数学公式总结 规律神器OEIS)

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。