[UVa11549]Calculator Conundrum
2024-08-31 13:45:26
题目大意:有一个只能显示n位数字的计算器,当溢出时只显示最高的n位。
输入k,要你不断平方,问你计算器显示的最大数是多少。
解题思路:这题的示数肯定会循环,那么我们关键就是找什么时候循环了。
可以用Floyd判圈法。
假设两个人在无限长的跑道上赛跑,一个人的速度是另一个的两倍,那么跑得快的永远在前面。
但是如果把跑道变成一个有限长的环,那么在某个时刻,速度快的一定会追上速度慢的。
我们也用这种方法,一个变量每次平方一遍,另一个平方两遍。当两个变量相等时说明循环了。
注意我们要记录的是最大答案,要在每次平方两遍的那个变量每次更新时都比较一遍(因为第一个变量可能跑不完一整个循环就被追上了)。
还有乘法中间过程会爆int,要用long long。
C++ Code:
#include<cstdio>
long long t1,t2;
const long long base[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,k,ans;
scanf("%d%d",&n,&k);
t1=t2=ans=k;
do{
t1=t1*t1;
while(t1>=base[n])t1/=10;
t2=t2*t2;
while(t2>=base[n])t2/=10;
if(ans<t2)ans=t2;
t2=t2*t2;
while(t2>=base[n])t2/=10;
if(ans<t2)ans=t2;
}while(t1!=t2);
printf("%d\n",ans);
}
return 0;
}
最新文章
- ui-router带参数的路由配置
- 正在编译转换: 未能找到元数据文件 EntityFramework.dll
- Java字节流:BufferedInputStream BufferedOutputStream
- MySQL、PostgreSQL、Ingres r3、MaxDB等开源数据库的详细比较
- 使用CodeDOM实现代码生成及动态编译
- debain上安装mono3.4.0和jexus5.5.2
- Centos6.5自带mysql的启动
- android菜鸟学习笔记7----android布局(二)
- mysql一些写常用命令
- 【HDOJ】4704 Sum
- git使用前配置
- Ubuntu下装QQ2012,让linux小白们不怕脱离windows
- PHP-无限级分类
- 图片与Base64相互转换 jar包
- Python机器学习笔记 K-近邻算法
- Latex中cls和sty文件有何区别?
- DB2常用函数详解(一):字符串函数
- HDU 1260:Tickets(DP)
- SpaceSyntax【空间句法】之DepthMapX学习:第四篇 凸多边形图分析[未完]
- ASP.NET MVC中切换模板页(不同目录的cshtml文件)