{sum+=i++} to Reach N
All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer less than (9*10^14+1) or (9E14 + 1) or (9*1014 +1) you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.
Input
The input file contains less than 1100 lines of input. Each line contains a single integer N (0<=N<= 9E14). Input is terminated by end of file.
Output
For each line of input produce one line of output. This line contains an integer which tells in how many ways N can be expressed as summation of consecutive integers.
Sample Input
9
11
12
Sample Output
3
2
2
1 comments:
one solution in c++:
#include iostream.h
// Explanation:
// It checks, for each value k, whether there is a sum of k consecutive
// terms that adds up to x. If we let m=0+1+2+...+(k-1), then there is
// such a sequence (namely, the one starting with the integer a) iff
// ak+m = x. To see whether such an a exists, we just check whether
// x-m is divisible by k. Since a must be at least 1, we also check
// that 1k+m <= x.
// This solution runs in time proportional to the square root of the
// input number, but it is much too slow . How
// could the problem be solved faster?
main() {
while (true) {
long long x;
cin >> x;
if (cin.eof()) break;
int t = 0;
long long m = 0;
for (long long k = 1; m+k <= x; k++) {
// invariant: m = 0+1+2+3+...+(k-1)
if ((x-m)%k == 0) t++;
m += k;
}
cout << t << "\n";
}
}
Post a Comment