Part 1 推导

题目描述经过我们精简，可以发现实际上是要我们求一个序列：

2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + ... + 2 ^ {63} = \sum_{i=0}^{63}

学过MO的同学看到这个式子应该很熟悉，我下面列举两种解法：

等比数列求和

等比数列求和公式证明如下：

本题中q = 2，带入等比数列求和公式得到：

S = 2 ^ {64} - 1

加上首项

q = 2的等比数列有一个特性（所以频频被考）。如果我们将原式加上2 ^ 0，可以得到如下结果：

2 ^ 0 + 2 ^ 0 = 2 ^ 1

2 ^ 1 + 2 ^ 1 = 2 ^ 2

2 ^ 2 + 2 ^ 2 = 2 ^ 3

...

2 ^ {63} + 2 ^ {63} = 2 ^ {64}

S = 2 ^ {64} - 1

可以看到与等比数列求和所得结果一模一样

Part 2 代码

Python

python内置了**用来求幂运算，如下代码可以求上方那个式子：

2 ** 64 - 1

结果为18446744073709551615，你会发现这怎么和标准答案不一样呢？其实是std是对答案进行了四舍五入。

手动舍入print(18446744073709552000)

正解：

def intRound(x, y):
    if ((x // (y // 10)) % 10) > 4:
        return (x // y + 1) * y
    else:
        return x // y * y
print(intRound(2 ** 64 - 1, 1000))

C++

__int128 O(n)

C++ 中可以使用pow来计算幂，但是2 ^ 64 - 1太大了，无法使用long long来存（long long极限为2 ^ 63 - 1），也不能使用pow。
一种方案是用_int128来存。

#include <cstdio>
using namespace std;
void _print(__int128 x) {
    if (x > 9) {
        _print(x / 10);
    }
    putchar(x % 10 + '0');
}
__int128 round(__int128 x, int y) {
    if (((x / (y / 10)) % 10) > 4) {
        return (x / y + 1) * y;
    } else {
        return x / y * y;
    }
}
int main()
{
    __int128 ans = 1;
    for (int i = 0; i < 64; i++) { // 手动求 2 ^ 64
        ans *= 2;
    }
    ans -= 1; // 进行 -1
    _print(round(ans, 1000)); // 取整后输出
}

scanf、printf、cin、cout均不支持__int128，这里参考了C++ __int128的使用这篇文章。

ull O(1)

比赛中是不能用__int128的。
诶，既然long long存不下，那么unsigned long long能不能存的下呢？
通过查表发现，unsigned long long的最大值：18446744073709551615
这个数字正好是本题的答案。

在头文件climits中记载了所有数据类型的最大值最小值。

#include <iostream>
#include <climits>
using namespace std;
unsigned long long round(unsigned long long x, int y) {
    if (((x / (y / 10)) % 10) > 4) {
        return (x / y + 1);
    } else {
        return x / y * y;
    }
}
int main()
{
    cout << round(ULLONG_MAX, 1000) << "000";
}

由于此题不四舍五入之前为ull的最大值，舍入后会溢出，需要手动加几个0。

如果谁能写一个更好看的round函数请在评论区中发出来:D。

参考：

1. C++ __int128的使用
2. 妈咪叔的latexlive编辑器