题目

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;
}