【题解】洛谷 P4759 [CERC2014]Sums_综合

题目传送门

题意：

一共有 $T$ 组数据，每组数据给定一个数 $N$ ，请将 $N$ 分解为几个连续正整数的和，如果有多种情况，请输出最小数最大的情况。

题解：

众所周知，这些连续的正整数为等差数列，而等差数列求和的公式为：
$\frac{1}{2}(a+b)t$
其中 $a$ 为首项， $b$ 为末项， $t$ 为项数。在这道题，由于公差为 $1$ ，所以项数为 $(b ? a + 1)$ 。带进去就是
$n=\frac{1}{2}(a+b)(b-a+1)$
$\frac{1}{2}(a+b)$ 就是从 $a$ 到 $b$ 的所有正整数的平均数。于是就可以得到一个结论：一些连续正整数的和为这些数的平均数乘以这些数的数量。

然而这道题知道的是和，现在求是哪些数。 $(a + b)$ 有两种可能——奇数或者偶数，除以 $2$ 之后得出的平均数会是整数或是小数（小数部分为 $0.5$ ）。然后我们依次枚举项数，反向求出平均数，若为整数或是小数部分为 $0.5$ 的数（这里要注意前后匹配，即偶数个项要为整数，奇数个项要为小数部分为 $0.5$ 的数）则判为合法。

这里要讲一下，如何判定一个数小数部分为 $0.5$ 。直接减也许可以，但这里讲另一种方法，没有浮点误差。我们判定的时候使用的是被除数与除数，假设分别为 $x$ 和 $y$ 。假设商小数部分为 $0.5$ ，那么
$\frac{x}{y}=\lfloor\frac{x}{y}\rfloor+0.5$
同时乘以 $2$ ，就变成了
$\frac{2x}{y}=2\lfloor\frac{x}{y}\rfloor+1$
然后左右同时乘 $y$ ，
$2x=2y\lfloor\frac{x}{y}\rfloor+y$
而 $\lfloor\frac{x}{y}\rfloor$ 是 C++ 中 int 的除法方式，因此没有浮点丢失。

inline bool point5(int x,int y){
    return 2*x==2*y*(x/y)+y;}

检查完毕之后就要输出。奇数个项的范围为 $(\lfloor\frac{n}{i}\rfloor-\lfloor\frac{i}{2}\rfloor)\sim(\lfloor\frac{n}{i}\rfloor+\lfloor\frac{i}{2}\rfloor)$ ，偶数个项的范围为 $(\lfloor\frac{n}{i}\rfloor-\frac{i}{2}+1)\sim(\lfloor\frac{n}{i}\rfloor+\frac{i}{2})$ 。

最后再补充一下枚举。枚举项数的顺序为从小到大，从 $2$ 开始。枚举到 $n$ 那是不可能的，绝对 TLE。由于题目要求的是正整数，根据上面的范围可以知道，只要 $\lfloor\frac{n}{i}\rfloor-\lfloor\frac{i}{2}\rfloor<0$ ，就不用再枚举了，直接跳出循环。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline bool point5(int x,int y)
{
    return 2*x==2*y*(x/y)+y;
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    int n;bool flag=0;scanf("%d",&n);for(int i=2;;i++){
    if(n/i-i/2<0) break;if(n%i==0&&i%2){
    printf("%d = ",n);for(int j=n/i-i/2;j<n/i+i/2;j++) printf("%d + ",j);printf("%d\n",n/i+i/2);flag=1;break;}else if(point5(n,i)){
    printf("%d = ",n);for(int j=n/i-i/2+1;j<n/i+i/2;j++) printf("%d + ",j);printf("%d\n",n/i+i/2);flag=1;break;}}if(!flag) printf("IMPOSSIBLE\n");}return 0;
}