algo基础板子
2025-08-16 11:34:00 #algo

基础板子

1. qucik pow

实质：$b$ 用二进制表示

1
2
3
4
5
6
7
8
9
10
int quickPow(int a, int b, int p){
    int ans=1;
    while(b){
        if(b&1)ans=(long long)ans*a%p;//一定要开longlong,否则会溢出
        //事实上要开两倍的长度
        a=(long long)a*a%p;
        b>>=1;
    }
    return ans;
}

2. 高精度(basic)

注意： 以下均默认 $a \geq 0, b \geq 0$，负数的情况需要另外判断 
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
string add(string& a, string& b){
    bool areSwap=false;
    if(a.size()<b.size()){
        areSwap=true;
        swap(a,b);
    }
    int i=a.size()-1;
    int j=b.size()-1;
    int carry=0;
    string ans;
    ans.reserve(a.size()+1);//预留较大的空间
    int na,nb=0;
    while(i>=0||j>=0||carry){//注意进位，实际上j>=0可以省略不写
        na=0,nb=0;
        if(i>=0)na=a[i--]-'0';
        if(j>=0)nb=b[j--]-'0';
        int sum=na+nb+carry;
        ans.push_back(sum%10+'0');
        carry=sum/10;
    }
    reverse(ans.begin(),ans.end());
    if(areSwap)swap(a,b);
    return ans;
}

string sub(string& a, string& b){
    bool areSwap=false;
    if(a.size()<b.size())areSwap=true;
    else if(a.size()==b.size()&&a<b)areSwap=true;//note:"9">"89"!
    if(areSwap)swap(a,b);
    int i=a.size()-1,j=b.size()-1,borrow=0;
    string ans;
    ans.reserve(a.size());
    int na=0,nb=0;
    while(i>=0){
        na=a[i--]-'0';
        nb=0;
        if(j>=0)nb=b[j--]-'0';
        int diff=na-nb-borrow;
        if(diff<0){
            diff+=10;
            borrow=1;
        }
        else borrow=0;//注意这个
        ans.push_back(diff+'0');
    }
    int n=ans.size();
    while(n>1&&ans[n-1]=='0')n--;//去除"后导"0，注意不要删完
    ans.resize(n);//注意resize保留的是前面的
    if(areSwap)ans.push_back('-');//注意加上负号
    reverse(ans.begin(),ans.end());
    if(areSwap)swap(a,b);
    return ans;
}

string mul(string& a, string& b){
    string ans;
    ans.resize(a.size()+b.size(),0);//预留足够空间
    for(int i=0;i<a.size();i++){
        for(int j=0;j<b.size();j++){
            int product=(a[a.size()-1-i]-'0')*(b[b.size()-1-j]-'0');
            ans[i+j]+=product;
            ans[i+j+1]+=ans[i+j]/10;
            ans[i+j]%=10;//注意这一部分的逻辑
        }
    }
    for(int i=0;i<ans.size();i++)ans[i]+='0';//到这里再转为字符，方便前面处理
    int n=ans.size();
    while(n>1&&ans[n-1]=='0')n--;
    ans.resize(n);
    reverse(ans.begin(),ans.end());
    return ans;
}

pair<string,string> divmod(string& a, string& b){
    assert(b!="0");
    if(a=="0")return {"0","0"};//这里要特判
    if(a.size()<b.size()||(a.size()==b.size()&&a<b))return {"0",a};//这里也要特判！！！
    string quotient,remainder;
    quotient.reserve(a.size()-b.size()+1);//空间不能小
    remainder="";
    for(char digit: a){
        remainder+=digit;
        int ind=0;
        while(ind<remainder.size()&&remainder[ind]=='0')ind++;
        remainder=remainder.substr(ind,remainder.size()-ind);//去除前导0, 注意不用留一个0
        int cnt=0;
        while(remainder.size()>b.size()||(remainder.size()==b.size()&&remainder>=b)){
            int i=remainder.size()-1,j=b.size()-1,borrow=0;
            string tmp;
            tmp.reserve(remainder.size());
            while(i>=0){
                int x=remainder[i--]-'0',y=0;
                if(j>=0)y=b[j--]-'0';
                int diff=x-y-borrow;
                if(diff<0){
                    diff+=10;
                    borrow=1;
                }
                else borrow=0;
                tmp.push_back(diff+'0');
            }
            int n=tmp.size();
            while(n>1&&tmp[n-1]=='0')n--;
            tmp.resize(n);
            reverse(tmp.begin(),tmp.end());
            remainder=tmp;
            cnt++;
        }
        if(cnt!=0||!quotient.empty())quotient.push_back(cnt+'0');//预处理前导零
    }
    if(remainder.empty())remainder="0";//注意这一句
    return {quotient,remainder};
}

3. 二分

  1. 找匹配到的最小的一个
1
2
3
4
5
6
7
8
9
int l=LL,r=RR,m,ans=-1;
while(l<=r){
    if(m>=nums){
        ans=m;
        r=m-1;
    }
    else l=m+1;
}
//自然地,ans=-1表示没有找到
  1. 找匹配到的最大的一个
1
2
3
4
5
6
7
8
int l=LL,r=RR,m,ans=-1;
while(l<=r){
    if(m>nums)r=m-1;
    else{
        ans=m;
        l=m+1;
    }
}
Prev
Next