 # AT CODER BEGINNER 190 D

can someone please help me with this ?

I could not get any way to solve it !!

1 Like

basically you need to find all divisors of 2n upto sqrt(2n) and then check whether (2n/ith divisor)-(ith divisor)-1 is divisible by 2 or not. if yes then increment the answer by 2

Can you please provide me with a soltn or a proof fr the same like how did u figure it out mathematically?

1 Like

Consider a sequence of n numbers
x,x+1,x+2,x+n-1
Where x is the first term of an AP of size n and common difference 1.
Now the sum of these terms must be equal to an initially given number say y
Then,
y = ((2x + n - 1)n)/2
On rearranging you will get,
2
x = (2
y)/n + 1 - n ;
Let the RHS of the above equation be z
Now cleary first of all, for x to exist, z must be an even number
Also, notice that n must be the divisor of the (2y) as seen in z
Hence iterate over all divisors of 2
y(could be done in O(sqrt(y))) and then compute z
If z is even, increment your answer, and you are done :).

2 Likes

Ok I will check and get back to you !! Thanks One basic observation is that an A.P. with a given sum starting with a positive number a can also be written as an A.P. starting with -(a-1). So the problem reduces to finding the number of A.P. starting with a positive number.
Now, let the A.P. starts with a and has c elements.
Then the sum of the A.P. can be written as
n = c(2a+c-1)/2
n - c(c-1)/2 = ac
Since both c and a can not be negative you can run a loop on c until c(c-1)/2 is less than n.
I have done similarly and you can view my submission here.

Can you tell me why did you increment count twice? @abhidot

here is my code: SY9iby - Online C++0x Compiler & Debugging Tool - Ideone.com

Why are you incrementing ans ? ans+=2? can I get intutuion for it?

if N is sum of a, a+1, a+2, … a+(n-1)(1)
then N is also sum -(a-1), -(a-2), … -2, -1, 0, 1, 2, …a-2, a-1, a, a+1, … a+(n-1)(1)
which is equivalent to a, a+1, …a+(n-1)(1)
that’s why if a sequence starting with positive integer found, it’s (say) equivalent sequence starting from negative number can also be found (for sequence starting with 1, it’s equivalent sequence will start from 0)
Hence incrementing ans by 2

1 Like

ok thanks gotcha!!

For every A.P. starting with a positive a and having c elements( ending with a+c-1 ), you can either start it from a or -(a-1) as adding numbers from -(a-1) to (a-1) adds up to zero only.

It’s similar to this problem.
Answer will be equal to `2 * no_of_ways + 2`.

Count the no. Of divisor that are odd , and multiply it with 2 .Refer AtCoder Beginner Contest 190 Announcement - Codeforces for proof