本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-02 16:19:55

P2669 [NOIP2015 普及组] 金币 讲解

题目

$O(n)$ 做法：

两层循环，第一层的 $i$ 表示第 $i$ 个周期（连续 $i$ 天），第二层的 $j$ 表示周期内在 $[1,i]$ 天，然后每次给 $ans$ 加上 $i$，最后输出即可。

$O(\sqrt n)$ 做法：

一层循环，考虑到第二层循环加了 $i$ 次 $i$，所以第二层循环可以去掉，在第一层循环加上 $i\times i$，时间复杂度是 $O(\sqrt n)$ 的。
虽说这已经很快了，但我们还可以用 $O(1)$ 做法完成。

$O(1)$ 做法：

推理平方差公式：

我们想一想，有没有一个公式快速的求出 $\sum_{i=1}^xi^2$ 呢？
$$\begin{aligned}\sum_{i=1}^ni^3-(i-1)^3&=n^3-(n-1)^3+(n-1)^3-(n-2)^3+\dots+1^3-0^3\&=n^3\end{aligned}$$ 以上等式成立，继续往下：
$$\sum_{i=1}^ni^3-(i-1)^3=n^3$$ $$\sum_{i=1}^ni^3-(i^3-3i^2+3i-1)=n^3$$ $$\sum_{i=1}^ni^3-i^3+3i^2-3i+1=n^3$$ $$(\sum_{i=1}^n3i^2-3i)+n=n^3$$ $$3(\sum_{i=1}^ni^2-i)+n=n^3$$ $$3(\sum_{i=1}^ni^2)-3(\sum_{i=1}^ni)+n=n^3$$ $$3(\sum_{i=1}^ni^2)-\frac{3n(n+1)}{2}+n=n^3$$ 我们设 $\sum_{i=1}^ni^2$ 为 $S(n)$，则：
$$3S(n)-\frac{3n(n+1)}{2}+n=n^3$$ $$6S(n)-3n(n+1)+2n=2n^3$$ $$6S(n)-3n^2-3n+2n=2n^3$$ $$6S(n)-3n^2-n=2n^3$$ $$6S(n)=2n^3+3n^2+n$$ $$S(n)=\frac{2n^3+3n^2+n}{6}$$ （标准的写法是 $\frac{n(n+1)(2n+1)}{6}$）

解一元二次方程：

方程 $n=\frac{x(x+1)}{2}$，变式： $$n=\frac{x^2+x}{2}$$ $$n=\frac{x^2}{2}+\frac{x}{2}$$ $$n=\frac{1}{2}x^2+\frac{1}{2}x$$ $$\frac{1}{2}x^2+\frac{1}{2}x-n=0$$ 得 $a=\frac{1}{2},b=\frac{1}{2},c=-n,\Delta=b^2-4ac$。
最后答案就是 $ans=\frac{-b+\sqrt\Delta}{2a}$，最后答案就是 $(n-\frac{ans(ans+1)}{2})\times(ans+1)+\frac{ans(ans+1)(2ans+1)}{6}$。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 0x2a2a2a2a
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,ans,num,ans2;
double a,b,c,delta; 
signed main(){
	FAST;
	cin>>n;
	a=b=0.5;
	c=-n;
	delta=b*b-4*a*c;
	ans=(-b+sqrt(delta))\/2\/a;
	num=ans*(ans+1)\/2;
	ans2=(2*ans*ans*ans+3*ans*ans+ans)\/6;
	n-=num;
	cout<<n*(ans+1)+ans2;
	return 0;
}