舍罕王的失算-O(1)解法（Python & C++）

1319 阅读 3 评论 0 点赞

# Part 1 推导

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

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

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

### 等比数列求和

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

[![等比数列公式证明](http://cat-shao.gitee.io/mypic/等比数列公式证明.png)](https://www.latexlive.com/#JTVDYmVnaW4lN0JhbGlnbiU3RCUwQVMlMjAmJTIwPSUyMHElMjAlNUUlMjAwJTIwKyUyMHElMjAlNUUlMjAxJTIwKyUyMHElMjAlNUUlMjAyJTIwKyUyMHElMjAlNUUlMjAzJTIwKyUyMC4uLiUyMCslMjBxJTIwJTVFJTIwbiUyMCU1QyU1QyUwQVMlMjAlNUN0aW1lcyUyMHElMjAmJTIwPSUyMHElMjAlNUUlMjAxJTIwKyUyMHElMjAlNUUlMjAyJTIwKyUyMHElMjAlNUUlMjAzJTIwKyUyMHElMjAlNUUlMjA0JTIwKyUyMC4uLiUyMCslMjBxJTIwJTVFJTIwJTdCbiUyMCslMjAxJTdEJTIwJTVDJTVDJTBBUyUyMCU1Q3RpbWVzJTIwcSUyMC0lMjBTJTIwJiUyMD0lMjBxJTIwJTVFJTIwJTdCbiUyMCslMjAxJTdEJTIwLSUyMHElMjAlNUUlMjAwJTIwJTVDJTVDJTBBUyUyMCYlMjA9JTIwJTVDZnJhYyU3QnElMjAlNUUlMjAlN0JuJTIwKyUyMDElN0QlMjAtJTIwcSUyMCU1RSUyMDAlN0QlN0JxJTIwLSUyMDElN0QlMjAlNUMlNUMlMEElNUNlbmQlN0JhbGlnbiU3RA==)

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

```latex
S = 2 ^ {64} - 1
```

### 加上首项

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

```latex
2 ^ 0 + 2 ^ 0 = 2 ^ 1
```

```latex
2 ^ 1 + 2 ^ 1 = 2 ^ 2
```

```latex
2 ^ 2 + 2 ^ 2 = 2 ^ 3
```

```latex
...
```

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

```latex
S = 2 ^ {64} - 1
```

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

# Part 2 代码

### Python

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

```python
2 ** 64 - 1
```

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

~~手动舍入`print(18446744073709552000)`~~

正解：
```python
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`来存。

```cpp
#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的使用](https://blog.csdn.net/xiao_k666/article/details/89431929)这篇文章。

#### ull O(1)

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

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

```cpp
#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的使用](https://blog.csdn.net/xiao_k666/article/details/89431929)
2. [妈咪叔的latexlive编辑器](https://www.latexlive.com/#JTVDYmVnaW4lN0JhbGlnbiU3RCUwQVMlMjAmJTIwPSUyMHElMjAlNUUlMjAwJTIwKyUyMHElMjAlNUUlMjAxJTIwKyUyMHElMjAlNUUlMjAyJTIwKyUyMHElMjAlNUUlMjAzJTIwKyUyMC4uLiUyMCslMjBxJTIwJTVFJTIwbiUyMCU1QyU1QyUwQVMlMjAlNUN0aW1lcyUyMHElMjAmJTIwPSUyMHElMjAlNUUlMjAxJTIwKyUyMHElMjAlNUUlMjAyJTIwKyUyMHElMjAlNUUlMjAzJTIwKyUyMHElMjAlNUUlMjA0JTIwKyUyMC4uLiUyMCslMjBxJTIwJTVFJTIwJTdCbiUyMCslMjAxJTdEJTIwJTVDJTVDJTBBUyUyMCU1Q3RpbWVzJTIwcSUyMC0lMjBTJTIwJiUyMD0lMjBxJTIwJTVFJTIwJTdCbiUyMCslMjAxJTdEJTIwLSUyMHElMjAlNUUlMjAwJTIwJTVDJTVDJTBBUyUyMCYlMjA9JTIwJTVDZnJhYyU3QnElMjAlNUUlMjAlN0JuJTIwKyUyMDElN0QlMjAtJTIwcSUyMCU1RSUyMDAlN0QlN0JxJTIwLSUyMDElN0QlMjAlNUMlNUMlMEElNUNlbmQlN0JhbGlnbiU3RA==)

0.0分

6 人评分

本文分类：题解列表
浏览次数：1319 次浏览
发布日期：2021-02-18 19:27:19
本文链接：https://blog.dotcpp.com/a/76830

上一篇 > 蓝桥杯算法提高VIP-快速幂（Java代码） 20行！！！
下一篇 > 单词得分（Java代码） 15行！！！

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

舍罕王的失算-O(1)解法（Python & C++）

评论列表共有 3 条评论

发表评论取消回复

舍罕王的失算-O(1)解法（Python & C++）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 3 条评论

发表评论 取消回复

评论列表共有 3 条评论

发表评论取消回复