个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2017-06-15 10:56:10
题目描述
1. 500位的数只能用数组或字符串表示，由于涉及到计算，用数组表示更方便；
2. 如果m=10^500, 那么对于任意大的整数n，n%m 即为n的后500位数；
3. 假如t1 = n1%m，其中n1是500位以内的数，那么t1也是500位以内的数；令n2是一个32bit可以表达的整数，那么（n1*n2)%m=(t1*n2)%m
4. 对于题目中给的n=2^p（p可能是一个较大的数），令k=2^27 (32bit只能最大表达 2^32 -1，那么实际上我们只能用到2^31, 考虑到k会乘一个10以内的数，需要预留4bit，那么k的指数只能取到27=31-4）， 那么n可以表示为：n=k*k*...*k*(2^(p')。
那么：
(2^p)%m = {k*k*...*k*(2^(p') }%m
将上式分步递归计算：t=（t*k）%m
最终的t就是我们期望的2^p的后500位数
经过上面分析，获取2^p的后500位就不难实现了。
另外，我还有一个问题，那就是计算2^p的位数。
2^p是一个很大的数，怎么用10进制数表达？最常用的就是科学计数法：
2^p=r * 10^h ( 1.0 <= r < 10.0)
那么h 1就是我们所求的位数。
对上式两边取10的对数：
h log10(r) = log10(2^p) = p*log10(2)
因为0<=log10(r) < 1, 那么 h <= p*log10(2) < h 1
那么:
h =floor(p*log10(2))
实现代码：
形如2^p-1的素数称为麦森数，这时p一定也是个素数。但反过来不一定，即如果p是个素数，2^p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是p=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入p（1000
输入格式
文件中只包含一个整数p（1000
输出格式
分析第一行：十进制高精度数2^p-1的位数。
第2-11行：十进制高精度数2^p-1的最后500位数字。（一行输出，不足500位时高位补0）
不必验证2^p-1与p是否为素数。
1. 500位的数只能用数组或字符串表示，由于涉及到计算，用数组表示更方便；
2. 如果m=10^500, 那么对于任意大的整数n，n%m 即为n的后500位数；
3. 假如t1 = n1%m，其中n1是500位以内的数，那么t1也是500位以内的数；令n2是一个32bit可以表达的整数，那么（n1*n2)%m=(t1*n2)%m
4. 对于题目中给的n=2^p（p可能是一个较大的数），令k=2^27 (32bit只能最大表达 2^32 -1，那么实际上我们只能用到2^31, 考虑到k会乘一个10以内的数，需要预留4bit，那么k的指数只能取到27=31-4）， 那么n可以表示为：n=k*k*...*k*(2^(p')。
那么：
(2^p)%m = {k*k*...*k*(2^(p') }%m
将上式分步递归计算：t=（t*k）%m
最终的t就是我们期望的2^p的后500位数
经过上面分析，获取2^p的后500位就不难实现了。
另外，我还有一个问题，那就是计算2^p的位数。
2^p是一个很大的数，怎么用10进制数表达？最常用的就是科学计数法：
2^p=r * 10^h ( 1.0 <= r < 10.0)
那么h 1就是我们所求的位数。
对上式两边取10的对数：
h log10(r) = log10(2^p) = p*log10(2)
因为0<=log10(r) < 1, 那么 h <= p*log10(2) < h 1
那么:
h =floor(p*log10(2))
实现代码：
点击(此处)折叠或打开
-
#incldue <math.h>
-
//mersenne number
-
static void bignumbermutil_500limit(unsigned int *rcd, int len, unsigned int key)
-
{
-
int i;
-
unsigned long long carry = 0;
-
unsigned long long sum;
-
-
for (i = 0; i < len; i)
-
{
-
sum = rcd[i] * key carry;
-
rcd[i] = sum % 10;
-
carry = sum / 10;
-
}
-
}
-
-
void printmersennenumber(int exp)
-
{
-
int len = (int)floor(log10(2) * exp) 1;
-
unsigned int rcds[501] = { 0 };
-
unsigned int mt = (unsigned int)(exp2(27));
-
int i;
-
-
rcds[0] = 1;
-
while (exp >= 27)
-
{
-
bignumbermutil_500limit(rcds, 501, mt);
-
exp -= 27;
-
}
-
if (exp > 0)
-
{
-
mt = (unsigned int)(exp2(exp));
-
bignumbermutil_500limit(rcds, 501, mt);
-
}
-
-
if (rcds[0] > 0)
-
{
-
rcds[0] -= 1;
-
}
-
else
-
{
-
int carry = -1;
-
int sum;
-
-
for (i = 0; i < 500 && carry < 0; i)
-
{
-
sum = rcds[i] carry 10;
-
rcds[i] = sum % 10;
-
carry = sum / 10 - 1;
-
}
-
}
-
-
printf("%d\n", len);
-
for (i = 499; i >= 0; i--)
-
{
-
printf("%c", '0' rcds[i]);
-
}
-
printf("\n");
- }
给主人留下些什么吧！~~