见链接
首先我们需要知道这两条公式： 1 + 2 + 3 + 4 + ⋯ + n = n × ( n + 1 ) 2 1+2+3+4+\dots+n=\frac{n\times(n+1)}{2} 1+2+3+4+⋯+n=2n×(n+1)
1 2 + 2 2 + 3 2 + 4 2 + ⋯ + n 2 = n × ( n + 1 ) × ( 2 n + 1 ) 6 1^2+2^2+3^2+4^2+\dots+n^2=\frac{n\times (n+1)\times (2n+1)}{6} 12+22+32+42+⋯+n2=6n×(n+1)×(2n+1) 然后让我们一起推一推 O ( 1 ) \operatorname O(1) O(1)公式吧！ 首先，由题意，设天数为 D D D，金币组数为 N N N，不满一组的为 R R R，则有： D = ( 1 + 2 + 3 + ⋯ + N ) + R ⇔ D = N × ( N + 1 ) + 2 R 2 ⇔ N 2 + N − 2 D ≈ 0 ∴ N = int ( − 1 + Δ 2 ) = int ( − 1 + 1 2 − 4 × 1 × ( − 2 D ) 2 ) = int ( 8 D + 1 − 1 2 ) ∴ N = int ( 8 × D + 1 − 1 2 ) D=(1+2+3+\dots+N)+R \\ \Leftrightarrow D=\frac{N\times(N+1)+2R}2 \\ \Leftrightarrow\ N^2+N-2D\approx0 \\ \therefore N=\operatorname{int}(\frac{-1+\sqrt\Delta}{2})\\ \qquad\qquad\qquad\qquad\qquad=\operatorname{int}(\frac{-1+\sqrt{1^2-4\times1\times(-2D)}}2) \\ \qquad\quad\ \ =\operatorname{int}(\frac{\sqrt{8D+1}-1}2) \\ \therefore N=\operatorname{int}(\frac{\sqrt{8\times D+1}-1}2) D=(1+2+3+⋯+N)+R⇔D=2N×(N+1)+2R⇔ N2+N−2D≈0∴N=int(2−1+Δ )=int(2−1+12−4×1×(−2D) ) =int(28D+1 −1)∴N=int(28×D+1 −1)
而基本组数 N N N与金币数 K K K的关系为 K = N × ( N + 1 ) × ( 2 × N + 1 ) 6 K=\frac{N\times (N+1)\times (2\times N+1)}{6} K=6N×(N+1)×(2×N+1) 所以不满一组的为 R R R与基本组数 N N N的关系为 R = ( N + 1 ) ( D − N ( N + 1 ) 2 ) R=(N+1)(D-\frac{N(N+1)}2) R=(N+1)(D−2N(N+1)) 所以答案 a n s ans ans与 N N N的关系是： a n s = N ( N + 1 ) ( 2 × N + 1 ) 6 + ( N + 1 ) ( D − N ( N + 1 ) 2 ) = N 3 3 + N 2 2 + N 6 − N 3 2 − N 2 − N 2 + N D + D = − N 3 6 − N 2 2 − N 3 + N D + D = N D ( N + 1 ) − N ( N 2 + 3 n + 2 ) 6 = N [ D − ( N + 1 ) ( N + 2 ) 6 ] + D ans=\frac{N(N+1)(2\times N+1)}{6}+(N+1)(D-\frac{N(N+1)}{2})\\ =\frac{N^3}3+\frac{N^2}2+\frac{N}6-\frac{N^3}2-N^2-\frac{N}2+ND+D\ \\ =-\frac{N^3}6-\frac{N^2}2-\frac{N}3+ND+D\qquad\qquad\qquad\quad\ \\ =ND(N+1)-\frac{N(N^2+3n+2)}6\qquad\qquad\qquad\ \\ =N[D-\frac{(N+1)(N+2)}6]+D\qquad\qquad\qquad\quad\ ans=6N(N+1)(2×N+1)+(N+1)(D−2N(N+1))=3N3+2N2+6N−2N3−N2−2N+ND+D =−6N3−2N2−3N+ND+D =ND(N+1)−6N(N2+3n+2) =N[D−6(N+1)(N+2)]+D 最后再用位运算什么的优化一下，就有： { a n s = N [ D − ( N + 1 ) ( N + 2 ) / 6 ] + D N = int ( ( s q r t ( D < < 3 + 1 ) − 1 ) < < 1 ) = int ( s q r t ( D < < 3 + 1 ) − 1 ) ) < < 1 \Big\lbrace ^{N=\operatorname{int}((sqrt(D\lt\lt3+1)-1)\lt\lt1)=\operatorname{int}(sqrt(D\lt\lt3+1)-1))\lt\lt1} _{ans=N[D-(N+1)(N+2)/6]+D} {ans=N[D−(N+1)(N+2)/6]+DN=int((sqrt(D<<3+1)−1)<<1)=int(sqrt(D<<3+1)−1))<<1 所以 C + + \operatorname C++ C++代码如下：
#include <bits/stdc++.h>//万能头 using namespace std;; int n, d, ans; int main() { cιn >> d; n = int(sqrt(D<<3+1)-1))<<1; ans = n*(d-(n+1)(n+2)/6)+d; couτ << ans; return 0; }最后祝复制我题解的人听取 W A \color{red}{WA} WA声一片！
2015年NOIP普及组第1题 ↩︎
