LuoguP4759 [CERC2014]Sums 题解
Content
给定 \(t\) 组数据,每组数据给定一个数 \(n\),判断 \(n\) 是否能够分解成连续正整数和,能的话给出最小数最大的方案。
数据范围:\(1\leqslant n\leqslant 10^9\)。
Solution
这道题如果暴力枚举的话,看数据范围就知道肯定会爆炸。因此我们要考虑推式子。
首先,我们设分解后的数列长度为 \(k\),首项为 \(a_1\)。那么显然得到 \(\text{(1)}\) 式:
\(\begin{aligned}n&=\dfrac{(a_1+(a_1+k-1))k}2\\&=\dfrac{(2a_1+k-1)k}2\end{aligned}\)
由于 \(a_1,k>0\),在 \(a_1>0\) 两边同时加上 \(a_1+k-1\) 得:
\]
然后我们由 \(\text{(1)}\) 式可得 \(2a_1+k-1=\dfrac{2n}{k}\),代入不等式:
\]
我们由样例可得 \(k\geqslant 2\)(读者自证不难),又因为 \(k\) 是正整数,所以得到了 \(k\) 的范围为:\(k\in[2,\left\lfloor\sqrt{2n}\right\rfloor]\)。
这样我们就可以考虑通过枚举 \(k\) 来求得答案。现在看 \(a_1\)。
我们还是通过 \(\text{(1)}\) 式求解:
\]
又因为 \(a_1\) 是正整数,所以只需要判断是否有下列条件成立即可:
- \(2k\mid(2n-k^2+k)\)。
- \(\dfrac{2n-k^2+k}{2k}>0\)
枚举出符合条件的方案我们就可以输出了,并且我们算一下不难发现,从 \(2\) 枚举到 \(\left\lfloor\sqrt{2n}\right\rfloor\) 第一个找出来的方案就是题目所要求的最小数最大的方案。注意输出的格式即可。如果枚举完了还是没有找到方案那就直接输出 IMPOSSIBLE
就好。
Code
int main() {
MT {
int n = Rint, flag = 1;
F(len, 2, (int)sqrt(2 * n)) {
if(!((2 * n - len * len + len) % (2 * len)) && (2 * n - len * len + len) / (2 * len) > 0) {
int a1 = (2 * n - len * len + len) / (2 * len);
printf("%d = ", n);
F(i, a1, a1 + len - 1) {
printf("%d ", i);
if(i != a1 + len - 1) printf("+ ");
else puts("");
}
flag = 0; break;
}
}
if(flag) puts("IMPOSSIBLE");
}
return 0;
}
最新文章
- JavaScript 日期选择器 Pikaday
- DNS枚举工具DNSenum
- .dwg(sw)-exb
- JavaScript中关于地址的获取
- Android和Linux应用综合对比分析
- struts2下s:iterator取不出值
- spring访问静态资源文件
- 【MYSQL】在脚本中使用变量-执行脚本时传参
- IntelliLock托管代码保护和许可授权管理系统软件详细介绍及下载
- volley(4) 请求参数:data:[ { bar_remain:XX , bar_code:";XX"; , bar_id: XX}], method:GET
- sql 2005 同义词
- [Objective-c 基础 - 2.7] 构造方法、重写init方法
- 点击轮播图片左右button,实现轮播效果
- Java采用JDBC的方式连接Hive(SparkSQL)
- SAP MM 可以不用创建盘点凭证直接录入盘点结果?
- python中的内置函数getattr()介绍及示例
- kafka清理数据日志
- 关于 redis的操作
- Debug模式下,测试app后缀名“-测试”
- .net面试题精选