I was trying to solve LightOJ 1278 this problem.
Problem statement : **Given an integer N, you have to find the number of ways you can
express N as sum of consecutive integers. You have to use at least two integers.
For example, N = 15 has three solutions, (1+2+3+4+5), (4+5+6), (7+8).**
Test cases : 200 , N <= 10^14
I came up with a O(sqrt(N)) solution like this , Try all possible lengths (length 2 to O(sqrt(N))) .
Code : —
int main()
{
int tc,cas = 0;
sfi(tc);
while(tc--)
{
ll N;
sfl(N);
int up_b = (sqrt(8*N+1) - 1)/2;
int ans = 0;
loop(len,2,up_b)
{
if((len&1))
{
if(N%len==0)
ans++;
}
else
{
ll temp = N - len/2;
if(temp!=0 && temp%len==0)
ans++;
}
}
CASE(cas);
pf("%d\n",ans);
}
return 0;
}
And I got TLE . I worked with some smaller N s and found out , that for all powers of 2 the answer is 0 , and for other numbers there 's a pattern with power , for example , ans[3] = 1, ans[9] = 2 , ans[27] = 3 . But , I couldn't find a way to exploit this. Need some hints to improve my run time .