Representing a Number
National Olympiad — Municipal round (2014 season)
Submission name: nsum.cpp
Problem summary
Count representations of N as a sum of one or more consecutive positive integers. The one-term representation N itself is included.
Input
The integer N.
Output
The number of representations.
Constraints
1 ≤ N ≤ 10^12; time limit 1 second.
Worked example
Official statement sample.
Input
15
Output
4
Solution analysis
- For length k and first term s, the sum is k*s+k(k−1)/2. The minimum possible sum for length k is k(k+1)/2, obtained at s=1, so only about sqrt(2N) lengths need checking.
- Rearrange to 2s=2N/k−k+1. A length is valid exactly when k divides 2N, the resulting expression is positive, and it is even. There is then exactly one starting value s for that length.
- For N=15 the valid lengths are 1,2,3,5, corresponding to 15; 7+8; 4+5+6; and 1+2+3+4+5. The loop stops before length 6 because even its minimum sum is 21.
Why it works
Every representation has a positive length satisfying the triangular-number bound, so the loop examines it. For each length the arithmetic-series equation uniquely determines the first term, and the divisibility, positivity, and parity checks are equivalent to it being a positive integer. Thus every representation is counted once.
Watch out. All products and 2N require 64-bit integers. Zero and negative first terms must not be counted.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long n;
cin>>n;
int answer=0;
// Length k forces 2*start = 2*N/k-k+1.
for(long long length=1;length*(length+1)/2<=n;++length){
if(2*n%length!=0){
continue;
}
long long twiceStart=2*n/length-length+1;
if(twiceStart>0&&twiceStart%2==0){
++answer;
}
}
cout<<answer<<'\n';
}