NYOJ 88-汉诺塔（一）【罗汉塔定理f(x)=2*f(x-1)+1,快速幂模板】

曾经终败给现在 2022-07-24 09:12 29阅读 0赞

## 汉诺塔（一） ##

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

现在请你计算出起始有m个金片的汉诺塔金片全部移动到另外一个针上时需要移动的最少步数是多少？（由于结果太大，现在只要求你算出结果的十进制位最后六位）

输入

第一行是一个整数N表示测试数据的组数(0<N<20)  
每组测试数据的第一行是一个整数m,表示起始时金片的个数。(0<m<1000000000)

输出

输出把金片起始针上全部移动到另外一个针上需要移动的最少步数的十进制表示的最后六位。

样例输入

2
    1
    1000

样例输出

1
    69375

来源

[\[张云聪\]原创][Link 1]

上传者

[张云聪][Link 2]

解题思路：

罗汉塔定理f（x）=f(x-1)\*2+1，化简之后我们发现就是快速幂。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    long long PowerMod(long long a, long long b, long long c)
    {
    	long long ans = 1;
    	a = a % c;
    	while(b>0)
    	{
    		if(b % 2 == 1)
    		ans = (ans * a) % c;
    		b = b/2;
    		a = (a * a) % c;
    	}
    	return ans;
    }
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	long long n;
    	while(t--)
    	{
    		scanf("%lld",&n);
    		long long cc=2;
    		long long dd=1000000;
    		long long ans=PowerMod(cc,n,dd)-1;
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E5%BC%A0%E4%BA%91%E8%81%AA%5D%E5%8E%9F%E5%88%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E5%BC%A0%E4%BA%91%E8%81%AA