Catshao

用户名：Catshao

访问量：28829

签　名：

stO KHIN Orz

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

　　自我简介：

TA的其他文章

【转载】四种最短路算法：Floyd，Dijkstra，Bellman-Ford，SPFA
浏览：224

【站外题解】小图灵热身赛T1-担担炮
浏览：233

记忆化搜索解法-题解（C++）
浏览：281

你可能喜欢

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

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

蓝桥杯2020年第十一届省赛真题-八次求和

　　作者: Catshao　　　　发表时间：2022-02-10 20:48:53 浏览：556　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-八次求和

这题 $$O(n)$$ 解法想必大家都会了吧？其实这题有个 $$O(1)$$ 解法。

![](/image_editor_upload/20220210084144_43407.gif)

式子既然有了就可以 $$O(1)$$ 计算。问题来了，这个式子是怎么来的。

前置知识：[牛顿插值法](https://www.bilibili.com/video/BV1T34y1S7fP) 。

~~通过百度我们知道~~ $$\sum\_{i = 1}^{n}i^k$$ 是一个 $$k + 1$$ 次多项式。既然知道是多项式就直接插值即可，得出上面求和的通项公式。

问题来了，为什么 $$\sum\_{i = 1}^{n}i^k$$ 是一个 $$k + 1$$ 次多项式？~~我也不知道~~，大家可以去看 [The Sum of the k-th Powers](https://codeforces.com/problemset/problem/622/F) 这道题。

--------------

贴一个 $$O(n)$$ 的代码，顺便提醒下开 `long long`

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

long long fastPow(long long a, long long b, long long m) {
    long long base = a, res = 1;
    while (b) {
        if (b & 1) {
            res = (res * base) % m;
        }
        base = (base * base) % m;
        b >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    long long sum = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        sum = (sum + fastPow(i, 8, 123456789)) % 123456789;
    }
    cout << sum << endl;
    return 0;
}
```

0.0分

2 人评分

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

Catshao

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯2020年第十一届省赛真题-八次求和

评论区

精彩推荐

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

母牛的故事（C语言代码）

化学品问题（C语言代码）

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

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

时间转换（Java代码）

【偶数求和】（C语言代码）

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

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

用筛法求之N内的素数。（C语言代码）

Catshao

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯2020年第十一届省赛真题-八次求和

评论区

精彩推荐

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

母牛的故事 （C语言代码）

化学品问题 （C语言代码）

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

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

时间转换 （Java代码）

【偶数求和】 （C语言代码）

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

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

用筛法求之N内的素数。 （C语言代码）

　　评论区

母牛的故事（C语言代码）

化学品问题（C语言代码）

时间转换（Java代码）

【偶数求和】（C语言代码）

用筛法求之N内的素数。（C语言代码）