P2669 [NOIP2015 普及组] 金币 讲解

· · 题解

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;
}