题目： 给定你一个数字 如：15
15可分解为
7+8
4+5+6
1+2+3+4+5
再如：
8
8不可分解为任何连续的正整数之和
所以输出NONE
此题就是给定一个数字如果这个数字可以分解为几个连续的正整数之和那么就输出所有的形式，如果不能就输出NONE
题解：
其实这道题目可以用到数学中最基础的等差公式的方式：设给定的数字为S
S = a1 + a2 + a3 + a4....
S = a1 + a1 + 1 + a1 + 2 + a1 + 3....设一共有i个
S = (a1 + a1 + i - 1) * i /2
首先我们讨论那些数不能分解为上面的形式
a1 + a1 + i - 1 和 i 这两个数肯定要么一个为偶数要么一个为奇数（自己脑补），所以他们成绩除2得出的数肯定得有奇数因子，而2^n不可能有奇数因子，所以不能被整除。
那么如何判断一个数是否为2的n次方？
int IsTwo(int n)
{
return (n&(n-1)) == 0 ? 1:0;
}
用此函数
n如果为2的n次方那么他的二进制表示肯定是第一位为1后面都是0
n-1恰好是最后一个是1其余多是0所以n&(n-1)肯定等于0
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int IsTwo(int n)
{
return (n&(n-1)) == 0 ? 1:0;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(IsTwo(n))
cout<<"NONE"<<endl;
else
{
int i,j,k;
for(i = 2; i<=n/2;i++)
{
if((2*n)%i == 0)
{
int temp = (2*n)/i+1-i;
if(temp%2 == 0&&temp/2!=0&&temp>=0)
{
int num = temp/2;
for(j = 0;j<i-1;j++)
{
cout<<num+j<<"+";
}
cout<<num+j<<endl;
}
}
}
}
}
return 0;
}
这就是代码楼 很简洁的o（n）级别的。 |
|
转播
