洛谷 P1045 麦森数
2024-08-30 06:24:29
题目描述
形如2^{P}-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2^{P}-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算2^{P}-1的位数和最后500位数字(用十进制高精度数表示)
输入输出格式
输入格式:
文件中只包含一个整数P(1000<P<3100000)
输出格式:
第一行:十进制高精度数2^{P}-1的位数。
第2-11行:十进制高精度数2^{P}-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证2^{P}-1与P是否为素数。
输入输出样例
输入样例#1:
1279
输出样例#1:
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
解题思路:
本题正确解法为高精度加快速幂,怎样求位数呢,公式:log10(2) * p + 1。再想如何求五百位,如果暴力一次次乘的话,会TLE,那么我们想到了快速幂,再加上高精度就AC了,需要注意的是题目只让求后五百位,所以我们每次只保存后五百位就可以了,因为前面无论是多少都不影响答案。
AC代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int p,f[],res[],sav[];
void rr1() {
memset(sav,,sizeof(sav));
for(int i = ;i <= ; i++)
for(int j = ;j <= ; j++)
sav[i+j-] += res[i] * f[j];//每一位都相乘,但是暂时不考虑进位
for(int i = ;i <= ; i++) {//进位
sav[i+] += sav[i] / ;
sav[i] %= ;
}
memcpy(res,sav,sizeof(res));//将sav赋值给res
}
void rr2() {
memset(sav,,sizeof(sav));
for(int i = ;i <= ; i++)
for(int j = ;j <= ; j++)
sav[i+j-] += f[i] * f[j];//每一位都相乘,但是暂时不考虑进位
for(int i = ;i <= ; i++) {//进位
sav[i+] += sav[i] / ;
sav[i] %= ;
}
memcpy(f,sav,sizeof(f));//将sav赋值给f
}
int main() {
scanf("%d",&p);
printf("%d\n",(int)(log10() * p + ));
res[] = ;
f[] = ;//高精度赋初值
while(p != ) {//快速幂过程
if(p % == ) rr1();
p /= ;
rr2();
}
res[] -= ;
for(int i = ;i >= ; i--)
if(i != && i % == ) printf("\n%d",res[i]);//50位就换行
else printf("%d",res[i]);
return ;
}
//NOIP普及 2003 T4
最新文章
- B-树,B+树,B*树详解
- javascript高级特性
- 在Android上实现使用Facebook登录(基于Facebook SDK 3.5)
- 使用 html5 postMessage 实现跨域
- Spring MVC 环境搭建(一)
- string为什么可以写入共享内存
- JS 鼠标事件大全
- 转:ORACLE制造方法的比较
- C语言清空输入缓冲区的N种方法对比
- Centos下安装配置LAMP(Linux+Apache+MySQL+PHP)
- php字符编码转utf-8格式
- lightoj 1236 正整数唯一分解定理
- 当浏览器不支持placeholder,所执行的函数
- Linux下的IO监控与分析
- Django中的权限系统
- mysql分区之range分区
- Vuex 教程案例:计数器以及列表展示
- HTML 浏览器抓包
- Js闭包学习笔记
- 人工智能-Selenium
热门文章
- 【Tomcat】tomcat logs 目录下各日志文件的含义
- POJ 3518 (后缀自动机)
- msp430入门学习23
- Ubuntu 16.04粘贴板增强工具Diodon
- windows下编译jpeg
- Zookeeper学习 &; Paxos
- php设计模式——模板模式
- 2015 Multi-University Training Contest 4 1001 Olympiad
- 【bzoj2748】[HAOI2012]音量调节
- 网关 192.168.2.1 114.114.114.114 dns查询