首页 > 代码库 > 汉诺塔(-) java modPow 的用法;
汉诺塔(-) java modPow 的用法;
汉诺塔(一)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
-
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵 天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金 片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消 灭,而梵塔、庙宇和众生也都将同归于尽。
现在请你计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少?(由于结果太大,现在只要求你算出结果的十进制位最后六位)
- 输入
- 第一行是一个整数N表示测试数据的组数(0<N<20)
每组测试数据的第一行是一个整数m,表示起始时金片的个数。(0<m<1000000000) - 输出
- 输出把金片起始针上全部移动到另外一个针上需要移动的最少步数的十进制表示的最后六位。
- 样例输入
2 1 1000
- 样例输出
1 69375
modPow:次方并求余;
代码:1 import java.math.BigInteger; 2 import java.util.Scanner; 3 4 public class Main{ 5 public static void main(String[] args) { 6 int n; 7 BigInteger m; 8 Scanner sc = new Scanner(System.in); 9 n = sc.nextInt(); 10 while (n-- > 0) { 11 m = new BigInteger(sc.next()); 12 System.out.println(new BigInteger("2").modPow(m,newBigInteger("1000000")).subtract(BigInteger.ONE)); 13 } 14 } 15 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。