AOJ 331.汉诺塔

175


题目



Description  


大家都听说过汉诺塔吧?有n个圆盘由小到大排列,套在a柱上,每次只能移动一个圆盘,而且只能大的在下,小的在上,让你把a柱上的圆盘移到b柱,给你一个多余的c柱,问你最少移动多少次才能完成任务。



Input  


输入有多组数据,每组包括一个整数n(n<=10000000),表示初始状态下有n个圆盘,当输入的n为0时,程序结束,n为负的情况不作处理。



Output  


对每个输入,对应一行输出,每行输出包括一个整数,即移动的最小次数,因为数目非常大,所以请对9973求余后再输出。



Sample Input  


1
2
3
4
0



Sample Output  


1
3
7
15


题解



求n个圆盘的汉诺塔的最少移动次数



找规律得 ans = 2n-1



由于最后要对9973取模,因此使用快速幂取模算法

另外要额外注意:如果n是负数,不输出

代码



//====================================================================
/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

typedef long long LL;

typedef long long LL;
LL exp_mod(LL a,LL n,LL b) {
    LL t;
    if(n == 0) return 1 % b;
    if(n == 1) return a % b;
    t = exp_mod(a,n / 2,b);
    t = t * t % b;
    if((n & 1) == 1) t = t * a % b;
    return t;
}

bool Do() {
    int n;
    if(scanf("%d",&n),n == 0)
        return false;
    if(n < 0)
        return true;
    printf("%lld\n",exp_mod(2,n,9973) - 1);
    return true;
}

int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论