一、高精度计算

这一次课程主要讲了高精度加、减、乘。

首先，定义一个高精度的结构体，储存这个数字的长度、和这个数字本身。

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
struct gaojing
{
    int n,z[2333];

    gaojing()
    {
        n=1;
        memset(z,0,sizeof(z));
    }
    
    void init()
    {
        scanf("%s",s+1);
        int l=strlen(s+1);
        reverse(s+1,s+l+1);

        n = l;
        for (int a=1;a<=n;a++)
            z[a] = s[a]-'0';
    }

    void print()
    {
        for (int a=n;a>=1;a--)
            printf("%d",z[a]);
    }
};

1、高精度加法

只需要将数字当做字符串读入，在一位一位地相加，考虑进位即可。

这里还需要注意的一点是，我们在写高精计算函数时，参数最好要读取地址，而不是直接读取字符串。这样如果这个字符串很大，参数进入时还要把这个很大的字符串复制一遍，既消耗时间，又消耗内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
gaojing operator+(const gaojing &a,const gaojing &b)
{
    gaojing c;
    c.n = max(a.n,b.n);
    for (int i=1;i<=c.n;i++)
        c.z[i] = a.z[i] + b.z[i];
    for (int i=1;i<=c.n;i++)
    {
        c.z[i+1] += c.z[i]/10;
        c.z[i] = c.z[i]%10;
    }
    if (c.z[c.n+1] != 0) c.n++;
    return c;
}

2、高精度比较

1
2
3
4
5
6
7
bool operator<(const gaojing &a,const gaojing &b)
{
    if (a.n!=b.n) return a.n<b.n;
    for (int i=a.n;i>=1;i--)
        if (a.z[i] != b.z[i]) return a.z[i]<b.z[i];
    return false;
}

3、高精度乘法

首先，根据十*十=百,十*百=千,千*万=千万可得：

i位*j位，结果要加到i+j-1位上。

最后，和高精度加法还有区别的一点是，这个要去除前导零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
gaojing operator*(const gaojing &a,const gaojing &b)
{
    gaojing c;
    c.n = a.n + b.n;
    for (int i=1;i<=a.n;i++)
        for (int j=1;j<=b.n;j++)
            c.z[i+j-1] += a.z[i] * b.z[j];
    for (int i=1;i<=c.n;i++)
    {
        c.z[i+1] += c.z[i]/10;
        c.z[i] = c.z[i]%10;
    }
    while (c.n != 1 && c.z[c.n] == 0)
        c.n--;
    return c;
}

4、高精度减法

其实思想和高精度加法差不多，只不过要判断正负（用刚才写的比较函数判断即可）。

代码就不再写了。

二、求最大公约数、最小公倍数。

可以用自带函数求最大公约数：

1
__gcd(a,b)；

推荐使用手写最大公因数：

1
2
3
4
5
int gcd(int a,int b)
{
    if (b==0) return a;
    else return gcd(b,a%b);
}

最小公倍数的话，根据两个数相乘等于他们的gcd*lcm即可求得。

三、快速幂：

首先，快速幂的目的就是做到快速求幂，假设我们要求a^b^,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)，快了好多好多。它的原理如下：

　　假设我们要求a^b^，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)^，例如当b=11时，$$a^{11}=a^{(2^{0}+2^{1}+2^{3})}$$

11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 $$a^{(2^{0})}a^{(2^{1})}a^{(2^{3})}$$，看出来快的多了吧原来算11次，现在算三次，但是这三项貌似不好求的样子….不急，下面会有详细解释。

　　由于是二进制，很自然地想到用位运算这个强大的工具： & 和 >> ，&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1=0为偶，x&1=1为奇。>>运算比较单纯,二进制去掉最后一位

1
2
3
4
5
6
7
8
9
10
11
int ksm(int x,int y,int p)
{
    int ans=1;
    while (y)
    {
        if (y&1) ans=1ll*ans*x%p;
        x=1ll*x*x%p;
        y>>=1;
    }
    return ans;
}

代码很短，死记也可行，但最好还是理解一下吧，其实也很好理解，以b==11为例，b=>1011,二进制从右向左算，但乘出来的顺序是 a^(2^0) * a^(2^1) * a^(2^3)，是从左向右的。我们不断的让base*=base目的即是累乘，以便随时对ans做出贡献。

　　其中要理解base*=base这一步，看base*base=base^2^,下一步再乘，就是base^2^base^2^=base^4^,然后同理 base^4^ * base^4^ = base^8^ ,,,,, see?是不是做到了base–>base^2^–>base^4^–>base^8^–>base^16^–>base^32^…….指数正是 2^i^ 啊，再看上面的例子，$$a^{(2^{0})}a^{(2^{1})}*a^{(2^{3})}$$，这三项是不是完美解决了，，嗯，快速幂就是这样。

四、矩阵内容

（这一部分我已经写过了，这里不再赘述）