【BZOJ 2656】2656: [Zjoi2012]数列(sequence) (高精度)
2024-09-17 10:25:37
2656: [Zjoi2012]数列(sequence)
Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 1499 Solved: 786Description
小白和小蓝在一起上数学课,下课后老师留了一道作业,求下面这个数列的通项公式:
小白作为一个数学爱好者,很快就计算出了这个数列的通项公式。于是,小白告诉小蓝自己已经做出来了,但为了防止小蓝抄作业,小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的,想出了一个绝妙的方法:即让小蓝说一个正整数N,小白则说出 的值,如果当N很大时小白仍能很快的说出正确答案,这就说明小白的确得到了公式。但这个方法有一个很大的漏洞:小蓝自己不会做,没法验证小白的答案是否正确。作为小蓝的好友,你能帮帮小蓝吗?
Input
输入文件第一行有且只有一个正整数T,表示测试数据的组数。
第2~T+1行,每行一个非负整数N。
Output
输出文件共包含T行。
第i行应包含一个不含多余前缀0的数,它的值应等于An(n为输入数据中第i+1行被读入的整数)
【样例输入】
Sample Input
31
3
10
Sample Output
1
2
3HINT
T<=20,N<=10^100
Source
【分析】
就是可以直接高精度暴力的。因为每次最多分出两个数而已。
比如:
$25→12,13→6,7→3,4→1,2→0,1$
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int mymax(int x,int y) {return x>y?x:y;} struct hugeint
{
int a[],l;
void clear()
{
memset(a,,sizeof(a));
l=;
}
friend hugeint operator + (hugeint x,hugeint y)
{
int ll=mymax(x.l,y.l);
for(int i=;i<=ll;i++) x.a[i]=x.a[i]+y.a[i];
for(int i=;i<=ll;i++) x.a[i+]+=x.a[i]/,x.a[i]%=;
while(x.a[ll+]!=) x.a[ll+]+=x.a[ll+]/,x.a[ll+]%=,ll++;
x.l=ll;
return x;
}
friend hugeint operator + (hugeint x,int y)
{
int ll=x.l; x.a[]+=y;
for(int i=;i<=ll;i++) x.a[i+]+=x.a[i]/,x.a[i]%=;
while(x.a[ll+]!=) x.a[ll+]+=x.a[ll+]/,x.a[ll+]%=,ll++;
x.l=ll;
return x;
}
friend hugeint operator / (hugeint x,int y)
{
int nw=;
for(int i=x.l;i>=;i--)
{
nw=nw*+x.a[i];
x.a[i]=nw/y;
nw%=y;
}
while(x.a[x.l]==&&x.l>) x.l--;
return x;
}
}; hugeint k1,k2;
void dfs(hugeint xx)
{
if(xx.l==&&xx.a[]==)
{
k1=xx;k2.clear();
return;
}
dfs((xx+)/);
if(xx.a[]&) k1=k1+k2;
else k2=k1+k2;
} char s[]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s+);
int l=strlen(s+);
hugeint xx;xx.clear();
for(int i=;i<=l;i++) xx.a[l-i+]=s[i]-'';
xx.l=l;
dfs(xx);
for(int i=k1.l;i>=;i--) printf("%d",k1.a[i]);
printf("\n");
}
return ;
}
最新文章
- 安装TFS2015后启用生成功能
- struts tags
- 快速傅里叶(FFT)的快速深度思考
- hadoop入门(3)&mdash;&mdash;hadoop2.0理论基础:安装部署方法
- 腾讯云环境配置之PHP5.6.3 + redis扩展 稳定版
- F2工作流引擎之 概述(一)
- 第2章 面向对象的设计原则(SOLID):2_里氏替换原则(LSP)
- matlab 中的textscan
- Java学习-026-类名或方法名应用之二 -- 统计分析基础
- c排序算法大全
- layout_weight体验(实现按比例显示)
- inux 下c/c++ 连接mysql数据库全过程-----已经通过验证
- hdu1728逃离迷宫 (利用最短路径思想+优先队列(BFS))
- HashMap完全解读
- 在Eclipse中设置文件的默认打开方式
- matlab获取向量中出现次数最多的元素
- HTML5新特性-多线程(Worker SharedWorker)
- Java项目访问resources文件
- Oracle-SQL-按月统计自助终端交易量
- Excel实现双击插入当前日期时间
热门文章
- [linux]ubuntu在线安装mysql
- POJ 1050 To the Max (最大子矩阵和)
- wepy开发小程序 大坑....本地调试ok,小程序上传体验版 组件出现问题
- CF 900B
- 2017ACM暑期多校联合训练 - Team 6 1010 HDU 6105 Gameia (博弈)
- Android 搭建Linux系统
- hdu 5326 Work(杭电多校赛第三场)
- 蓝色的cms企业记账管理后台模板源码——后台
- 图片轮播器——jquery插件
- linux脚本学习之路-在suse10环境中生存指定大小指定文件名的压缩文件