蓝桥杯第二次培训--数论

雨点打透心脏的1/2处 2021-05-16 20:37 278阅读 0赞

## 最大公约数 ##

指两个或多个整数共有约数中最大的一个

### 质因数分解法 ###

质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。

例如
    6=2*3
    4=2*2
    相同的有2
    所以2就是4,6的最大公约数

### 辗转相除法 ###

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

例如
    120 50
    120%50=20
    50%20=10
    20%10=0
    
    10就是120和50的最大公约数

代码

int gcd(int a,int b)
    { 
    	if(a%b==0){ 
    		return b;
    	}
    	else{ 
    		//cout<<b<<" "<<(a%b)<<endl; 
    		gcd(b,a%b);
    	}
    }

#include <bits/stdc++.h>
    
    using namespace std;
    
    int gcd(int a,int b)
    { 
    	if(a%b==0){ 
    		return b;
    	}
    	else{ 
    		//cout<<b<<" "<<(a%b)<<endl; 
    		gcd(b,a%b);
    	}
    }
    int main()
    { 
    	
    	int a=50;
    	int b=120;
    	cout<<gcd(a,b);
    	
    	
     }

不知道大家和我有没有一样的疑问，原来我认为我写的这个函数只有a大于b的才能运行，其实不然，不管a大于b还是a小于b都是一样的

### 最小公倍数 ###

当会了最大公因数后，最小公倍数就很简单了

a和b的最大公因数是d
    a和b的最小公倍数就为 a*b/d  记住公式就可以了
    
    但是注意一下， a*b有可能会溢出，爆出int的范围，所以更恰当的写法是 a/d*b

这里顺便也说一下 int的范围 大约在10的9次方左右  
long long 的范围在10的18次方左右

有时候根据题目给的范围选择合适的，如果发现出现了负数或者数字很离谱很有可能就是溢出的原因

## 素数 ##

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

### 普通方法求素数 ###

bool isprime(int n){ 
    	if(n<=1){ 
    		return false;
    	}
    	int sqr=(int)sqrt(n*1.0);
    	for(int i=2;i<=sqr;i++){ 
    		 if(n%i==0){ 
    		 	return false;
    		 }
    	}
    	return true;
    }

大家想想为什么可以通过求根号来优化算法

### 埃氏筛选法 ###

素数的倍数一定不是素数

埃氏筛选法的思想:首先将2到n范围内的整数写下来，其中2是最小的素数。将表
    中所有的2的倍数划去，表中剩下的最小的数字就是3，他不能被更小的数整除，
    所以3是素数。再将表中所有的3的倍数划去……以此类推，如果表中剩余的最小的
    数是m，那么m就是素数。然后将表中所有m的倍数划去，像这样反复操作，就能依
    次枚举n以内的素数。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODY2MTUz_size_16_color_FFFFFF_t_70_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int ans[maxn]; //全局变量自动赋值为0 
    bool pri[maxn];
    int num;
    void findprime()
    { 
    	for(int i=2;i<maxn;i++){ 
    		if(pri[i]==0){ 
    			ans[num++]=i;
    			for(int j=i+i;j<maxn;j+=i)
    			{ 
    				pri[j]=true;
    			}
    		}
    	} 
    }
    int main()
    { 
    	findprime();//注意一定不要忘记调用函数了 
    	for(int i=0;i<100;i++){ 
    		cout<<ans[i]<<" ";
    		if(i%10==0){ 
    			cout<<endl;
    		}
    	}
    	return 0;
    }

### 线性筛（了解即可） ###

线性筛的核心就是每次晒的时候保证是用在小质因子筛去的  
线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了  
当n比较小的时候两种筛法速度差不多

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1e6+10;
    int n,num;
    int ans[maxn];//ans数组用来存放质数
    bool p[maxn];//p[i], i为质数则为false否则为true
    
    void find_prime(int n){ 
    	for(int i=2;i<=n;i++){ 
    		if(p[i]==false){ 
    			 ans[num++]=i;
    		}
    		for(int j=0;j<num&&ans[j]<=n/i;j++){ 
    			 //对于任意一个合数x，假设pj为x最小质因子，当i==x/pj时，一定会被筛掉
    			 p[ans[j]*i]=true;
    			 if(i%ans[j]==0){ 
    			 	break;
    		//1.i%pj == 0,因为pj是从小到大枚举的 pj定为i最小质因子，pj也定为pj*i最小质因子
    		//2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
    			 }
    		}
    	}
    }

## 大数运算，高精度 ##

当有时候数字非常大的时候甚至都超出了longlong范围时，那我们该怎么算能，这就用到高精度算法了

这里提点题外话，python是真的香，本身就支持大数，也就是说苦逼的c语言要要写一大堆，别人python能直接算

### 高精度加法 ###

#include <iostream>
    #include <string>
    #include <algorithm> 
    #include <vector>
    using namespace std;
    vector<int> a,b,c;
    
    
    vector<int> add(vector<int> &a,vector<int> &b){ 
      if(a.size()<b.size()){ 
       return add(b,a);//一两个数最长的那个为基准
      }
      int t=0;
      
      for(int i=0;i<a.size();i++){ 
       t+=a[i];
       if(i<b.size()){ //当b的当前位还有数的时候加b[i]
        t+=b[i];
       }
       c.push_back(t%10);//当前位压入c
       t=t/10;//进位
      }
      if(t){ 
       c.push_back(t);//判断最高位是否有进位
       
      } 
      return c;//别忘记返回
      }
    
    int main()
    { 
    	
     string s1,s2;
     cin>>s1>>s2;
     
     for(int i=s1.length()-1;i>=0;i--){ 
     	a.push_back(s1[i]-'0');
     } 
     for(int i=s2.length()-1;i>=0;i--){ 
     	b.push_back(s2[i]-'0');
     }	
    
      c=add(a,b);
      for(int i=c.size()-1;i>=0;i--)
      { 
      	cout<<c[i]; 
      }	
    }

### 高精度减法 ###

#include <iostream>
    #include <string>
    #include <algorithm> 
    #include <vector>
    using namespace std;
    vector<int> a,b,c;
    bool cmp(vector<int> a,vector<int> b){  //判断a和b谁大 
    	if(a.size()!=b.size()){ 
    		 return a.size()>b.size();//如果长度不相等，长度大的大 
    	}
    	else{ 
    		for(int i=a.size()-1;i>=0;i--){ //注意要从最高位开始比较
    			if(a[i]!=b[i]){ 
    				return a[i]>b[i];//如果长度相等，从最高位往最低为做比较大的大 
    			}
    		}
    		return true;//相等返回真 
    	}
    	
    }
    vector<int> sub(vector<int> a,vector<int>b){ 
           vector<int> c;
    	   for(int i=0,t=0;i<a.size();i++){ //t是借位 
    	        t=a[i]-t;//当i小于b的长度时a[i]-b[i]-t 否则a[i]-t 
    	        if(i<b.size()){ 
    	            t=t-b[i];
    	        }
    	        c.push_back((t+10)%10);//如果t小于0就向高位借一位，t大于0直接存起来。模10就把两种情况写一起 
    	        if(t<0){ 
    	            t=1;
    	        }
    	        else{ 
    	            t=0;
    	        }
    	   }
    	   while(c.size()>1&&c.back()==0){ 
    	       c.pop_back();//消除前导零 
    	   }
    	   return c;//别忘记返回值
    } 
    
    int main()
    { 
    	
     string s1,s2;
     cin>>s1>>s2;
     
     for(int i=s1.length()-1;i>=0;i--){ 
     	a.push_back(s1[i]-'0');
     } 
     for(int i=s2.length()-1;i>=0;i--){ 
     	b.push_back(s2[i]-'0');
     }	
    
       if(cmp(a,b))
       { 
       	c=sub(a,b);
       }
       else{ 
       c=sub(b,a);
       }
      for(int i=c.size()-1;i>=0;i--)
      { 
      	cout<<c[i]; 
      }	
    }

### 高精度乘法 ###

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    vector<int> mul(vector<int> a,int b){ 
    	vector<int> c;
    	int t=0;
    	for(int i=0;i<a.size();i++){ 
    		  t=a[i]*b+t;
    		  c.push_back(t%10);
    		  t=t/10;
    	}
    	while(t){ 
    		c.push_back(t%10);//可能有不止一位进位 
    		t=t/10;
    	}
    	return c;
    }
    
    int main()
    { 
        string s1;
        vector<int> a,c;
        int b;
        cin>>s1>>b;
       for(int i=s1.length()-1;i>=0;i--)
        { 
        	a.push_back(s1[i]-'0');
    	}
        c=mul(a,b);
        for(int i=c.size()-1;i>=0;i--){ 
        	cout<<c[i];
    	}
        
        return 0;
    }

### 高精度除法 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    using namespace std;
    
    vector<int> div(vector<int> a,int b,int &r){ 
    	vector<int> c;
    	
    	for(int i=a.size()-1;i>=0;i--){ //从高位到低位除以除数 
    	         r=r*10+a[i];
    	       	 c.push_back(r/b);
    	       	 r=r%b;
    		   
    	}
    	reverse(c.begin(),c.end());
    	while(c.size()>1&&c.back()==0){ 
    		c.pop_back();//消除前导零 
    	}
    	return c;
    }
    
    int main()
    { 
        string s1;
        vector<int> a,c;
        int b,r=0;
        cin>>s1>>b;
       for(int i=s1.length()-1;i>=0;i--)
        { 
        	a.push_back(s1[i]-'0');
    	}
        c=div(a,b,r);
        for(int i=c.size()-1;i>=0;i--){ 
        	cout<<c[i];
    	}
        cout<<endl<<r;//输出余数 
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODY2MTUz_size_16_color_FFFFFF_t_70_pic_center]: /images/20210516/4ded3a7e8ee9435aaffb34af96a86bc6.png