Catshao

用户名：Catshao

访问量：25964

签　名：

stO KHIN Orz

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

　　自我简介：

TA的其他文章

人类智慧分块
浏览：160

你可能喜欢

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

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

优质题解

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

　　作者: Catshao　　　　发表时间：2021-02-18 19:27:19 浏览：1084　|　评论：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编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

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的其他文章

你可能喜欢

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

C语言训练-求素数问题（C语言代码）

上车人数（C语言代码）

转化为字符数组

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

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

评论区

精彩推荐

采药（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

字符串的输入输出处理（C语言代码）

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

【亲和数】（C语言代码）

c primer plus 第十二章 12.1小节

小明A+B （C语言代码）

ASCII帮了大忙

Catshao

TA的其他文章

你可能喜欢

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

C语言训练-求素数问题 （C语言代码）

上车人数 （C语言代码）

转化为字符数组

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

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

评论区

精彩推荐

采药 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

字符串的输入输出处理 （C语言代码）

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

C语言训练-委派任务* （C语言代码）..................竟然是第一个

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

【亲和数】 （C语言代码）

c primer plus 第十二章 12.1小节

小明A+B （C语言代码）

ASCII帮了大忙

C语言训练-求素数问题（C语言代码）

上车人数（C语言代码）

　　评论区

采药（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

字符串的输入输出处理（C语言代码）

【亲和数】（C语言代码）