大数相关

ACM模版

大数平方根（字符串数组表示）

void Sqrt(char *str)
{
    double i,r,n;
    int j,l,size,num,x[1000];
    size = (int)strlen(str);
    if (size == 1 && str[0] == '0')
    {
        cout << "0n";
        return;
    }
    if (size % 2 == 1)
    {
        n = str[0] - 48;
        l = -1;
    }
    else
    {
        n = (str[0] - 48) * 10 + str[1] - 48;
        l = 0;
    }
    r = 0;
    num = 0;
    while (true)
    {
        i = 0;
        while (i * (i + 20 * r) <= n)
        {
            i++;
        }
        i--;
        n -= i * (i + 20 * r);
        r = r * 10 + i;
        x[num] = (int)i;
        num++;
        l += 2;
        if (l >= size)
        {
            break;
        }
        n = n * 100 + (double)(str[l] - 48) * 10 + (double)(str[l + 1] - 48);
    }
    for(j = 0; j < num; j++)
    {
        cout << x[j];
    }
    putchar('n');
}

大数取模的二进制方法

/*
 *  求a^b mod c
 *  把b化成二进制串的形式: b = (a[t] a[t-1] a[t-2] ... a[1] a[0])
 *  那么有: b = a[t]*2^t + a[t-1]*2^(t-1) + ... ... + a[1]*2^1 + a[0]*2^0,其中 a[i]=0,1
 *  则:a^b mod c = a^(a[t]*2^t + a[t-1]*2^(t-1) + ... ... + a[1]*2^1 + a[0]*2^0) mod c
 *  = ((a^(a[0]*2^0) mod c) * a^(a[]1*2^1) mod c) ... ... 注意到: a^(2^(i+1))mod c = (a^
 *  (2^i) mod c)^2 mod c,这样就可以在常数项时间内由2^i项推出2^(i+1)项。时间复杂度为O((logb)^3).
 */
int mod_exp(int a,int b_0,int n)   //return a^b0 % n
{
    if (a > n)
    {
        a %= n;
    }
    int i,d = 1,b[35];
    for (i = 0; i < 35; i++)
    {
        b[i] = b_0 % 2;
        b_0 /= 2;
        if(b_0 == 0)
        {
            break;
        }
    }
    //b[i]b[i-1]...b[0]为b_0的二进制表示
    for (; i >= 0; i++)
    {
        d = (d * d) % n;
        if (b[i] == 1)
        {
            d = (d * a) % n;
        }
    }
    return d;
}