c++ - 河内塔 - Long Int 无法处理结果 - 在 C++ 上使用时间戳

Question

我正在尝试解决 Urionlinejudge.com 上的挑战，问题（见下文）要求计算解决河内塔问题所需的时间并输出结束的小时（HH:MM:SS 格式）。

输入是磁盘的数量，输出是解决的小时数（认为每次移动需要一秒钟）。

我知道这个算法在 (2^n) - 1 中增长。

主要问题是，如果输入很大，则“long int”无法处理结果，因为它具有指数增长。

我尝试使用“for”来解决这个问题，并在 24 小时后减去数字，因为问题不问需要多少天，它只问问题结束当天的小时数。

但是，我超过了最大运行时间。我能做些什么？

#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    if (n < 17)
    {
        n = pow(2, n);
        n--;
    }
    else
    {
        int j = 1;
        for (int i = 0; i < n; i++)
        {
            j *= 2;
            if (j >= 86400)
            {
                j -= 86400;
            }
        }
        n = j - 1;
    }
    int second, minute, hour;
    if (n >= 86400)
    {
        n = n % 86400;
    }
    if (n >= 3600)
    {
        hour = n / 3600;
        minute = n % 3600;
        if (minute >= 60)
        {
            second = minute % 60;
            minute = minute / 60;
        }
        else
        {
            minute = 0;
            second = n;
        }
    }
    else if (n >= 60)
    {
        hour = 0;
        minute = n / 60;
        second = n % 60;
    }
    else
    {
        hour = 0;
        minute = 0;
        second = n;
    }

    cout << setw(2) << setfill('0') << hour << ":" << setw(2) << setfill('0')
            << minute << ":" << setw(2) << setfill('0') << second << endl;
    return 0;
}

问题：

(...) 问题由 3 个引脚组成，第一个引脚中有一堆圆盘，一个比另一个大。众所周知，不允许将较大的磁盘放在较小的磁盘之上。这意味着，要从堆中转移一个磁盘，必须首先移除所有较小的磁盘。除此之外，一次只允许移动一个磁盘。

当所有磁盘从第一个引脚转移到第三个引脚时，问题就解决了。

我们知道猴子从午夜 (00:00:00) 开始工作，它们每天 24 小时不间断地工作，移动每个磁盘至少需要 1 秒钟。你的任务是以 hh:mm:ss 格式预测白天或晚上的确切时间，即猴子最早完成游戏和世界结束的时间。

输入 输入由包含单个整数 0 < X < 10 ⁴⁰的单行组成，即起始堆栈中的磁盘数。

输出 输出由格式为 A:B:C 的字符串组成，其中 0 ≤ A < 24 e 0 ≤ B, C < 60 (HH:MM:SS) 格式。

来源：https ://www.urionlinejudge.com.br/judge/en/problems/view/2681

标签： c++timestamp