[51nod1138]正整数分解为几个连续自然数之和
2024-08-29 18:26:04
解题关键:注意为什么上界是$\sqrt {2n} $
因为函数是关于m的递减函数,而结果必须为正整数
$a = \frac{{2n + m - {m^2}}}{{2m}} = \frac{n}{m} + \frac{1}{2} - \frac{m}{2}$
将$\sqrt {2n} $带入,结果为$\frac{1}{2}$,正好保证了结果不为负,因为函数是单调递减的,所以也不需判断结果是否为负。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
bool flag=false;
int t=sqrt(*n);
for(int i=t;i>=;i--){
int t1=*n+i-i*i;
int t2=*i;
if(t1%t2==){
flag=true;
cout<<t1/t2<<endl;
}
}
if(!flag) cout<<"No Solution\n";
return ;
}
第二个问题是什么样的数可以写成连续n个自然数之和,什么样的数不能?
通过编程实验发现,除了2^n以外,其余所有数都可以写成该形式。下面说明为什么。
若数M符合条件,则有M=a+(a+1)+(a+2)+…+(a+n-1)=(2*a+n-1)*n/2,而2*a+n-1与n肯定一个为奇数一个为偶数,即M一定要有一个奇数因子,而所有2^n都没有奇数因子,因此肯定不符合条件。
再证明只有M有一个奇数因子,即M!=2^n,M就可以写成连续n个自然数之和。假设M有一个奇数因子a,则M=a*b。
1)若b也是奇数,只要b-(a-1)/2>0,M就可以写成以b-(a-1)/2开头的连续a个自然数;将这条结论里的a和b调换,仍然成立。15=3*5=1+2+3+4+5=4+5+6.
2)若b是偶数,则我们有一个奇数a和一个偶数b。
2.1)若b-(a-1)/2>0,M就可以写成以b-(a-1)/2开头的连续a个自然数。24=3*8=7+8+9.
2.2)若(a+1)/2-b>0,M就可以写成以(a+1)/2-b开头的连续2*b个自然数。38=19*2=8+9+10+11.
上述两个不等式必然至少有一个成立,所以可以证明,只要M有一个奇数因子,就一定可以写成连续n个自然数之和。
最新文章
- C# 合并及拆分PDF文件
- SQL SERVER2012附加 (PS:开始试过sql2012直接附加失败)
- android 返回键 操作
- mfc 调用Windows的API函数实现同步异步串口通信(源码)
- bind绑定多个事件切换
- js组件之间的通信
- ES5特性之Object.freeze
- 你不知道的Java类
- Java和C++中的static
- memcpy、memmove、memset
- Strom-7 Storm Trident 详细介绍
- PullToRefreshScrollView 修改下拉刷新图标
- MySQL5.6 windows7下安装及基本操作
- 清华集训2014 day2 task3 矩阵变换
- [国嵌攻略][153][I2C裸机驱动设计]
- Django练习——TodoList
- P1_jemeter安装--jdk安装
- Zabbix监控mysql主从(二)
- kettle杂记
- python-自定义异常,with用法
热门文章
- selenium之坑(StaleElementReferenceException: Message: Element not found in the cache...)
- Linux Shell 下的输出重定向
- Stream computing
- Yii2学习笔记---内附GridView配置总结
- 第二十四篇、socketserver源码剖析
- SQl Server 中登录名 、用户、角色、概念一览
- form表单验证失败,阻止表单提交
- jQuery绿色下拉网站导航
- linux下安装rpm格式的mysql
- MySQL--开发技巧(一)