NYOJ------汉诺塔(一)
2024-10-21 05:59:36
汉诺塔(一)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
-
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
现在请你计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少?(由于结果太大,现在只要求你算出结果的十进制位最后六位)
- 输入
- 第一行是一个整数N表示测试数据的组数(0<N<20) 每组测试数据的第一行是一个整数m,表示起始时金片的个数。(0<m<1000000000)
- 输出
- 输出把金片起始针上全部移动到另外一个针上需要移动的最少步数的十进制表示的最后六位。
- 样例输入
-
2
1
1000 - 样例输出
-
1
69375 此题属于乘方取模....所谓乘方取模,就是对于1~--很大的数,即便就是O(n),也会超时。且满足 a ^m -b m为偶数 ;
sum={ 比如2^8=((2*2)^2)^2----这样原来需要经过8次才能完成的,现在才需要3次......a^m -b m为奇数;
同样道理,原来的需要O(n)的现在优化之后变为O(log2(n)),速度快得不行啦!!........
对此,贴上自己的代码.....
#include<iostream>
#define mod 1000000
using namespace std;
int main()
{
int n;
long long m;
long long count;
long long sum;
cin>>n;
while(n--)
{
cin>>m;
count=;
sum=;
while(m)
{
if(m&)
{
sum*=count;
sum%=mod;
}
count*=count;
count%=mod;
m>>=;
}
cout<<sum-<<endl;
}
return ;
}
最新文章
- Database first with EntityFramework (Migration)安装和升级
- Android版-支付宝APP支付
- Cron 表达式详解和案例
- 使用Visual Studio Code开发Asp.Net Core WebApi学习笔记(八)-- 多环境开发
- FontMetrics ----- 绘制文本,获取文本高度
- PHP利用微信跳转的Code参数获取用户的openid
- Go语言结构体(struct)
- 从成本角度看Java微服务
- 实现全屏轮播,并且轮播div中的文字盒子一直自动垂直居中
- 4.variables
- 基于JDK1.8的LinkedList剖析
- mysql事务隔离级别详解和实战
- Java中字符串相加和字符串常量相加区别
- js如何判断数字是否有小数
- eclipse中的web项目部署路径
- Numpy详解
- python遍历目录os.walk(&#39;&#39;d:\\test2";,topdown=False)
- Unix/Linux系统管理技术手册学习笔记——shell
- Qt,Qt/E,Qtopia Core, Qtopia之间的区别和联系
- 学习计划 mysql 主从复制