Catshao

用户名：Catshao

访问量：28812

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

　　作者: Catshao　　　　发表时间：2021-02-18 19:27:19 浏览：1166　|　评论：1　

原题链接：C语言训练-舍罕王的失算

# 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分

18 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

int

#include <bits/stdc++.h>
using namespace std;

int main()
{
	unsigned long long sum=0,n=1;
	for(int i=0;i<64;i++){
		sum+=n;
		n*=2;
	}
	cout<<sum<<endl;
}

2022-11-06 14:49:03

Catshao

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

矩形面积交（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-计算1977！* （C++代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

大小写转换（C语言代码）

妹子杀手的故事（C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

Pascal三角（C语言代码）

C语言训练-大、小写问题（C语言代码）

Catshao

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

矩形面积交 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-计算1977！* （C++代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

大小写转换 （C语言代码）

妹子杀手的故事 （C语言代码）

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

Pascal三角 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

矩形面积交（C语言代码）

大小写转换（C语言代码）

妹子杀手的故事（C语言代码）

Pascal三角（C语言代码）

C语言训练-大、小写问题（C语言代码）