高精度算法


  • 大数的存储
    • 思路大概就是把数以字符串的形式读入,然后将它们一位一位倒叙存进一个整形数组。
  • 高精度加法
    • 把每一位相加,若有进位就将下一位加一。
  • 高精度乘法 与高精度加法类似。
  • 示例代码
    #include<bits/stdc++.h>
    using namespace std;
    string s1,s2;
    int input(string &s,int a[],int &len){
        cin>>s;
        len=s.length();
        for(int i=0;i<len;i++){
            a[i]=s[len-i-1]-'0';
        }
        return len;
    }
    int plus_(int a[],int b[],int lena,int lenb,int c[]){//O(n)
        int lenc=0;
        while(lenc<lena||lenc<lenb){
            c[lenc]=a[lenc]+b[lenc];
            if(c[lenc]>=10){
                c[lenc]-=10;
                c[lenc+1]++;
            }
            lenc++;
        }
        if(c[lenc]==0){
            lenc--;
        }
        return lenc;
    }
    int time_(int a[],int b[],int lena,int lenb,int c[]){//O(n^2)
        int lenc;
        for(int i=0;i<lenb;i++){
            for(int j=0;j<lena;j++){
                c[i+j]+=a[j]*b[i];
                lenc=i+j;
            }
        }
        lenc+=20;
        for(int i=0;i<2000;i++){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
        while(c[lenc]==0){
            lenc--;
        }
        return lenc;
    }
    int main(){
        int a[2000],lena,b[2000],lenb,c[2000],lenc;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(a));
        memset(c,0,sizeof(a));
        input(s1,a,lena);
        input(s2,b,lenb);
        lenc=time_(a,b,lena,lenb,c);
        for(int i=lenc;i>=0;i--){
            cout<<c[i];
        }
        cout<<endl; 
        memset(c,0,sizeof(c));
        lenc=plus_(a,b,lena,lenb,c);
        for(int i=lenc;i>=0;i--){
            cout<<c[i];
        }
    }

快速幂

  • $a^bmodc;a,b,c\\le 10^9$
  • 代码见Day1

进制转换

  • 从10进制转其他进制
  • 代码:

    #include<bits/stdc++.h>
    using namespace std;
    char s[100];
    int tot;
    int main(){
        int a[20000];
        int b=121;
        int tobase=2;
        cin>>b>>tobase;
        while(b>0){
            a[tot++]=b%tobase;
            b/=tobase;
        }
        for(int i=tot-1;i>=0;i--){
            printf("%d",a[i]);
        }
        return 0;
    }
  • 从其它进制转10进制
  • 代码:
    #include<bits/stdc++.h>
    using namespace std;
    char s[100];
    int main(){
        int base;
        cin>>base;
        scanf("%s",s);
        int x=1;
        int num=0;
        int l=strlen(s);
        for(int i=l-1;i>=0;i--){
            int a = s[i]-'0';
            if(a>=base){
                cout<<"Error!";
                return 0;
            }
            num += a*x;
            x *= base;
        }
        cout<<num;
        return 0;
    }

素数

  • 大于一且因数只有1和它本身。
  • 算数基本定理
    • 任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积$N=P\_1^{a\_1}\\times P\_2^{a\_2}\\times P\_3^{a\_3}\\times ......\\times P\_n^{a\_n}$,这里$P\_1
  • 判断一个数是不是素数
  • 一般算法 cpp #include<bits/stdc++.h> using namespace std; bool is_prime(int x){ for(int i=2;i*i<=x;i++){ if(x%i==0) return 0; } return 1; } int main(){ int n; cin>>n; cout<<is_prime(i); return 0; }
  • $O(nloglogn)$算法 cpp #include<bits/stdc++.h> using namespace std; bool a[100000005]; int x[100000005]; int find_prime(int n){ int tot=0; for(int i=2;i<=n;i++){ if(!a[i]){ x[tot++]=i; for(int j=2;j*i<=n;j++){ a[j*i]=1; } } } return tot; } int main(){ int len=find_prime(100000); for(int i=0;i<len;i++){ cout<<x[i]<<" "; } return 0; }

gcd/lcm

  • gcd:最大公约数
  • lcm:最小公倍数
  • $(a,b)\[a,b\]=ab$

gcd

  • $gcd(a,b)=p\_1^{min(a\_1,b\_1)}\\times p\_2^{min(a\_2,b\_2)}\\times ...\\times p\_n^{min(a\_n,b_n)}$
  • 怎么算?
  • 辗转相减 $gcd(a,b) = gcd(b,a-b)$
  • 辗转相除法 $gcd(a,b) = gcd(b,a\\%b)$
  • 代码如下: cpp int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }

lcm

  • $lcm(a,b)=p\_1^{max(a\_1,b\_1)}\\times p\_2^{max(a\_2,b\_2)}\\times ...\\times p\_n^{max(a\_n,b_n)}$
  • 代码如下: cpp int lcm(int a,int b){ return a*b/gcd(a,b); }

示例代码

    #include<bits/stdc++.h>
    using namespace std;
    int gcd(int a,int b){
        if(b==0) return a;
        return gcd(b,a%b);
    }
    int lcm(int a,int b){
        return a*b/gcd(a,b);
    }
    int main(){
        cout<<gcd(3,4)<<endl;
        cout<<lcm(3,4);
        return 0;
    } 

裴蜀定理

  • $gcd(a,b)=d\\Rightarrow ax+by=d$
  • $gcd(a,b)=1\\Leftarrow\\Rightarrow ax+by=1$
Last modification:March 14th, 2020 at 09:04 pm