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 << "0\n";
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;
}