进制转换

不用字符串模拟的情况

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main(){
    unsigned int n;
    while (cin>>n) {
        vector<int> arr;
        while(n){
            arr.push_back(n%2);
            n/=2;
        }
        for(int i=arr.size()-1;i>=0;i--){
        cout<<arr[i];
        }
    cout<<endl;
    }
    return 0;
}

核心：

首先取余数，然后整除2
vector存储，之后逆序输出，但是如果用栈不用了

下面是用栈解决的情况：

#include <iostream>
#include<stack>

using namespace std;

int main(){
    unsigned int num;
    stack<int> s;
    while(cin>>num){
        while(num){
            s.push(num%2);
            num/=2;
        }
        while(!s.empty()){
            cout<<s.top();
            s.pop();
            //因为这里有pop，所以可以将stack在循环外定义，不用针对每个二进制数建立一个stack
        }
        cout<<endl;
    }
}

需要用字符串模拟的情况

在很多时候题目暗示了数字会很大（30位），在这种情况下用整型就无法表示了。一些基本数据类型的范围如下：
图片说明

例题
进制转换
来源：牛客网

将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

输入描述:
多组数据，每行为一个长度不超过30位的十进制非负整数。
（注意是10进制数字的个数可能有30个，而非30bits的整数）

输出描述:
每行输出对应的二进制数。

//这个数据会太长，所以需要用字符串模拟
#include <iostream>
#include<string>
#include<vector>

using namespace std;
//需要重写除法

string Div(string a ,int x){
    int remain=0;
    for(int i=0;i<a.size();i++){
        int current=remain*10+a[i]-'0';//余数*10+后一位除以x即可
        a[i]=current/x+'0';//保存形式是字符，所以应该加‘0’
        remain=current%x;
    }
    int pos=0;
    while(a[pos]=='0')
        pos++;
    return a.substr(pos);//去除前置多余的0
}

int main(){
    string str;
    while(cin>>str){
        vector<int> ve;
        while(str.size()!=0){
            ve.push_back((*(str.end()-1)-'0')%2);
            //ve.push_back(str[str.size()-1]-'0')%2);
            str=Div(str, 2);
        }
        for(int i=ve.size()-1;i>=0;i--)
            cout<<ve[i];
        cout<<endl;
    }
    return 0;
}

字符串除法模版

string Div(string a ,int x){
    int remain=0;
    for(int i=0;i<a.size();i++){
        int current=remain*10+a[i]-'0';//余数*10+后一位除以x即可
        a[i]=current/x+'0';//保存形式是字符，所以应该加‘0’
        remain=current%x;
    }
    int pos=0;
    while(a[pos]=='0')
        pos++;
    return a.substr(pos);//去除前置多余的0
}

记忆点⚠️：

需要一个余数变量remain和一个当前的被除数变量current
遍历字符串
cur=re*10+a[i]-'0';a[i]=cur/x+'0';remain=current%x;
使用一个数组就行了，不必开辟新的数组
需要将前置的多余的0去掉（substr）

字符串乘法模版

string Multiple(string str,int x){
    int carry=0;
    for(int i=str.size()-1;i>-1;i--){
        int cur=x*(str[i]-'0')+carry;
        str[i]=cur%10+'0';
        carry=cur/10;
    }
    if(carry)
        str="1"+str;
    return str;
}

字符串加法模版

string Add(string str,int x){
    int carry=x;
    for(int i=str.size()-1;i>-1;i--){
        int cur=(str[i]-'0')+carry;
        str[i]=cur%10+'0';
        carry=cur/10;
    }
    if(carry)
        str="1"+str;
    return str;
}

⚠️记忆点：

进位carry和当前cur
cur=x*(str[i]-'0')+carry.算str[i]，算carry
cur=str[i]-'0'+carry.算str[i]，算carry

最大公因数/公倍数模版

//递归版
int GCD(int a,int b){
    if(!b)
        return a;
    else
        return GCD(b, a%b);
}
//非递归版
int gcd(int a,int b) {
    if(!b)
        return a;
    int c;
    while(b) {
        c=b;
        b=a%b;
        a=c;
    }
}
//lcm
int LCM(int a,int b){
    return b/gcd(a,b)*a;
    //先除后乘，以免a*b溢出
}

素数

素数的判断分为筛法和非筛法，其中筛法更加重要和常用。

非筛法

非筛法针对于判断某个数是否是素数，只需要在[2,bound]内判断是否可以整除就行，但是很明显sqrt()函数是一个计算起来比较困难的函数，不应该在for循环中使用这个函数，应该提前定义一个变量将其计算出来。

筛法

如果要判断某个范围内有多少素数，那么用暴力遍历的方法就不好了（时间复杂度太大），必须用筛法解决。

//素数筛法
#include <iostream>
#include <cstdio>
#include<vector>
using namespace std;
const int MAXN=10001;

vector<int> prime;
bool isPrime[MAXN];

void Initial(){
    for(int i=0;i<MAXN;i++){
        isPrime[i]=true;
    }
  //全部初始化为true,即首先默认全是素数
    isPrime[0]=false;
    isPrime[1]=false;
    for(int i=2;i<MAXN;i++){
        if(!isPrime[i])
            continue;
          //如果是素数，就推入向量
        prime.push_back(i);
          //从i^2开始之后i的倍数都是素数，i到i*i之间不必算（i*k（k<i））已经被k的倍数计算过了，可以理解成某种剪枝
        for(int j=i*i;j<MAXN;j+=i)
            isPrime[j]=false;
    }
    return;
}

注意点⚠️：

prime向量存储素数；isPrime数组判断是不是素数
数组初始化全部是true，isPrime[0]=false; isPrime[1]=false;
从2到MAXN，如果isPrime为假就跳过；如果为真就将i放入向量中并从i*i开始的每个倍数都将isPrime设置为真

快速幂

LL qpow(LL a, LL b, LL MOD) {//a 的 n 次方（可取模）
  LL ans = 1;
  while (b) {
    if (b & 1) {
      //若当前位是1
      ans *= a;
      ans %= MOD;
    }
    b >>= 1;
    //byouyiyiwei
      a *= a;
      a %= MOD;
    }
  return ans;
}

总体思想就是：每次都要将a平方，然后根据b当前位数上是否为1来决定需不需要在这个位置上累乘

第五篇博客——数学问题