杂项

秦久韶算法/honer规则

1
2
3
4
5
6
7
8
9
10
11
12
ll sum(int n, vector<int> &a, int x)
{
    ll ans = 0;
    ll mid = 1;
    for (int i = 0; i <= n; i++)
    {
        ans = (ans + (a[i] % MOD * mid % MOD) % MOD) % MOD;
        mid = (mid * x) % MOD;
    }
    return ans;
}
//带入x求f(x);f(x)=a0*x0+a1*x1...

大数相乘

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
#include<iostream>
#include<string>
using namespace std;
//移位进位法
string Mul(string left, string right)
{
 	size_t Lsize = left.size();		//size_t = unsigned int
    size_t Rsize = right.size();
    size_t Size = Lsize + Rsize;	//最长位数
    string res(Size, '0');

    int takevoer = 0;//进位
    int offset = 0;//移位

    size_t idx = 1, j = 1;
    for (idx = 1; idx <= Rsize; ++idx)
    {
        takevoer = 0;
        int rightnum = right[Rsize - idx] - '0';
        //计算每一位与left相乘
        for (j = 1; j <= Lsize; ++j)
        {
            char resBit = res[Size - j - offset] - '0';		//取res存储对应位的数字
            int num = rightnum * (left[Lsize - j] - '0') + takevoer + resBit;//将两个数相乘，将进位和数组内存的数加入
            takevoer = num / 10;
            res[Size - j - offset] = num % 10 + '0';		//先把个位存进去
        }
        if (takevoer != 0)
            res[Size - j - offset] = takevoer + '0';
        offset++;
    }

    //如果没有进位的话，res最高位没有数字
    if (res[0] == '0')
        res.erase(0, 1);
    if(res[0]=='0')
        return "0";
    return res;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string str1;
        string str2;
        cin >> str1 >> str2;
        string ans=Mul(str1,str2);
        cout<<ans<<"\n";
    }
    return 0;
}

快速幂

此处∗*可以不只代表简单乘法，base也可换成其他类型。

1
2
3
4
5
6
7
8
9
10
11
12
ll quickPower(ll base,int power)
{
    ll res=1;
    while(power>0)
    {
        if(power%2==1)
            res*=base;
        bas*=base;
        power/=2;
    }
    return res;
}