清北学堂（2019 5 1） part 4

今天讲数论

1.进制问题（将n转换成k进制数）：

　　1.方法：短除法

　　　将n/k，保存，将商当做新的n，将余数保存，直到商为0，将余数（包括0），倒序输出，即得n的k进制数

2.关于高精四则运算（我本以为不用怎么整的）：

　　举个加和乘的例子...

　　众所周知，a+b problem是最简单的红题，再加个*也无伤大雅，代码如下（没文件头）：

int main(){

    int a,b;

    cin>>a>>b;

    cout<<a*b;

    return ;

}

　　直到你加了这些东西：

 #include<bits/stdc++.h>

 using namespace std;

 struct nu{

     int a[];

     int l;

     nu(){

         l=;

         memset(a,,sizeof(a));

     }

     friend istream& operator>>(istream &cin,nu &x){  //意思是:重载>>（用于cin，读到x里面）

         static char s[];

         cin>>s;

         int l=strlen(s);

         for(int i=;i<=l;i++)

             x.a[i]=s[l-i-]-'';

         x.l=l;

         return cin;

     }

     friend ostream& operator<<(ostream &cout,const nu &x){   //与上面大同，多了个const，在于使x值在输出前后值相同

         for(int i=x.l-;i>=;i--)

             cout<<x.a[i];

     }

 };

 nu operator+(const nu &x,const nu &y){    //重载+

     nu ans;

     int len=max(x.l,y.l);

     for(int i=;i<len;i++)

         ans.a[i]+=x.a[i]+y.a[i];

     for(int i=;i<len;i++){

         if(ans.a[i]>=){

             int now=ans.a[i]/;

             ans.a[i+]+=now;

             ans.a[i]%=;

         }

         while(ans.a[len+]) len++;

     }

     ans.l=len;

     return ans;

 }

 nu operator*(const nu &x,const nu &y){    //重载*用了非常简单而经典的高精算法

     nu ans;

     for(int i=;i<x.l;i++)

         for(int j=;j<y.l;j++)

             ans.a[i+j]+=x.a[i]*y.a[j];

     ans.l=x.l+y.l;

     for(int i=;i<ans.l;i++){

         ans.a[i+]+=ans.a[i]/;

         ans.a[i]%=;

     }

     while(ans.l>&&!(ans.a[ans.l]))

         ans.l--;

     ans.l++;

     return ans;

 }

 int main(){

     nu a,b;

     cin>>a>>b;

     cout<<a*b;

     return ;

 }

　　6-9行是构造函数，用于memset

　　10-22是重载cin与cout，背过就好

　　加const的原因是进行运算的值由符号返回，而从不是变量本身，所以没有赋值的话不能改变变量的值，也更方便电脑理解，可以看到stl里面好多函数用了const

　　至于&符号，用因如下：

　　每次用函数运算时，每个函数形如 f(int n)，都要把用的变量“n”的值拷贝一份进行运算，如果引用数组就更慢，还更占内存，用了&符号意在免去拷贝操作，直接引用其值，

　　（反正有了const不用怕数值变化）这就算一个优化

　　后面一直到主函数之前都是重载运算符

3.关于素数（又是各种筛法）

　　粘下模板：

　　1.埃氏筛：

#include<bits/stdc++.h>

using namespace std;

bool no[]={,};

int pri[];

int tot;

inline void p(int t){

    for(int i=;i<=t;i++)

        if(!no[i]){

            pri[++tot]=i;

            for(int j=i+i;j<=t;j+=i)

                no[j]=;

        }

}

int n;

int main(){

    scanf("%d",&n);

    p(n);

    for(int i=;i<=tot;i++)printf("%d\n",pri[i]);

    return ;

}

　　欧拉筛（线性筛）：

#include<bits/stdc++.h>

using namespace std;

bool no[];

int pri[];

int tot;

int n;

inline void p(int n){

    for(int i=;i<=n;i++){

        if(!no[i])

            pri[++tot]=i;

        for(int j=;j<=n&&i*pri[j]<=n;j++){

            no[i*pri[j]]=;

            if(!(i%pri[j])) break;

        }

    }

}

int main(){

    scanf("%d",&n);

    p(n);

    for(int i=;i<=tot;i++)printf("%d\n",pri[i]);

    return ;

}

　　3.exgcd：

#include<bits/stdc++.h>

using namespace std;

int a,b,x,y;

inline int exgcd(int a,int b,int &x,int &y){      //利用性质gcd（a,b）=gcd（b,a%b）

    if(!b){

        x=;

        y=;

        return a;

    }int g=exgcd(b,a%b,x,y);

    int t=x;

    x=y;

    y=(t-(a/b)*x);

    return g;

}

int main(){

    cin>>a>>b;

    exgcd(a,b,x,y);

    if(x<) x+=b;

    cout<<x;

    return ;

}

　　练多了不解释...

　　下午考试了..我..应该..大概不会爆零

巴特西

清北学堂（2019 5 1） part 4

最新文章

热门文章