首页 > 程序开发 > 软件开发 > 其他 >

快速幂 XDOJ

2017-04-24

快速幂 XDOJ:汉诺塔是一个非常好玩的游戏。 XDU ACM 2014 级女队的 nanf0621 经常和队友 Aloes 和 liuhanx1 一起玩汉诺塔。

快速幂 XDOJ:汉诺塔是一个非常好玩的游戏。 XDU ACM 2014 级女队的 nanf0621 经常和队友 Aloes 和 liuhanx1 一起玩汉诺塔,很久之后她们觉得很无聊,于是给自己增加了点难度,将每个盘子复制一份。那么她们希望知道,最少需要多少步,才能将 2n 个盘子从 A 杆移动到 C 杆?

普通汉诺塔的规则如下(摘自维基百科):

有三根杆子 A, B, C。 A 杆上有 n 个穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:
? 每次只能移动一个圆盘。
? 大盘不能叠在小盘上面。
此题则是,有三根杆子 A, B, C。 A 杆上有 2n 个穿孔圆盘,盘的尺寸由下到上单调不增,每种尺寸的盘子有 2 个。要求按下列规则将所有圆盘移至 C 杆:
? 每次只能移动一个圆盘。
? 大盘不能叠在小盘上面,大小相同的盘可以互相叠放。
因为 nanf0621 也被杜神坑过,非常讨厌高精度,她希望知道答案对 2097151的模。

输入格式

输入包含多组数据(至多 1000 组),请处理至文件结束。
每组数据包含一个整数 n ,表示有 2n 个盘子。
输入保证 1 ≤ n ≤ 1018。

输出格式

对于每组数据输出 1 行,即最少移动步数对 2097151 的模。

输入输出样例

输入样例

1
2

输出样例

2
6


汉诺塔移动的最少步数

递推公式 A(n+1) = 2A(n)+1

假设层数为n的汉诺塔需要最少A(n)次移动,那么n+1个汉诺塔,先将n个汉诺塔从A移到B,需要A(n)步,将第n+1个汉诺塔移动到C,需要1步,最后将B上的n个塔移动到C,需要A(n)步。

公式 A(n) = 2^n - 1


思路

此题本质是计算2*(2^n - 1),由于n非常大(1 ≤ n ≤ 1018),所以如何求2^n至关重要。此处用到了快速幂算法。


快速幂

先放上代码

int poww(int a,int b){
    int ans=1,base=a;
    while(b!=0){
        if(b&1!=0) //检查b二进制最后一位是不是0
          ans*=base;
        base*=base;
        b>>=1; //b右移一位
  }
    return ans;
}

代码

#include
#define M 2097151

long long n;

long long poww(long long a, long long n)
{
    long long ans = 1, base = a;
    while(n != 0)
    {
        if(n&1 != 0) ans *= base % M;
        base *= base % M;
        n >>= 1;
    }
    return ans;
}

int main()
{
    while(scanf("%lld", &n) == 1)
    {
        printf("%lld\n", ( ( poww(2, n) - 1 )%M*2 )%M );
    }
    return 0;
}
相关文章
最新文章
热点推荐