PROBLEM LINK:Author: Kevin Atienza DIFFICULTY:Simple PREREQUISITES:Arithmetic series PROBLEM:Given $N$ and $C$, is there an arithmetic series with positive integral terms, positive common difference, exactly $N$ terms and a sum of $C$? QUICK EXPLANATION:It's sufficient to check if there is such a series with common difference $1$ or $2$. To check if a series exists with a common difference $d$, check if $2C  (N1)Nd$ is positive and divisible by $2N$. EXPLANATION:Common differenceThe problem would be easier if we know the common difference, say $d$, between the terms in the arithmetic series, because knowing this, the number of terms, and the sum, is enough to extract the elements of the arithmetic series. Specifically, remember that if $a$ is the first term, then the terms of the series are
$$a, a + d, a + 2d, \ldots, a + (N1)d$$ However, we require the terms to be positive integers, so we need to check if $a$ is a positive integer. Here's how we can do it:
These are very simple to implement! Which common differenceUnfortunately, we don't know the value of $d$. It may be the case that more than one $d$ is valid, or no $d$ is valid. So which ones do we check? Clearly, we can't try all values in the range $1 \le d \le C$ because $C$ is very large! Let's consider an example: $C = 112$ and $N = 7$. The answer for this case is As another example, consider $C = 81$ and $N = 6$. In this case, we have the following series: $$\begin{align*} 1 + 6 + 11 + 16 + 21 + 26 &= 81 \\\ 6 + 9 + 12 + 15 + 28 + 21 &= 81 \\\ 11 + 12 + 13 + 14 + 15 + 16 &= 81 \end{align*}$$ Note that the average value in this case is $81/6 = 13.5$, which is not an integer, but that's okay. Here's another observation: The arithmetic series with the largest first term seems to be the one with the smallest common difference, as in the examples above. This kinda makes sense, because given the common difference $d$ and the average value $C/N$, we can actually compute the first term: The difference between the first and last term is $(N1)d$, so the difference between the average and the first term must be $d(N1)/2$. Thus, the first term must be $C/N  d(N1)/2$! (Note that this is the same as the formula we got above.) In this formula, the smaller the $d$, the larger the first term, so the series with the largest first term is the one with the smallest $d$! What does this mean for us? Well, since we want all terms to be positive, we only need to check the arithmetic series with the largest possible first term. If the first term of this series is not positive, then we can be sure that no valid series exists, because the first term of all other series are smaller! Thus, we only need to check the series with the smallest possible $d$. Finally, how do we then determine this $d$? Well, notice that if $C/N  d(N1)/2$ is an integer, and we let $d' = d2$, then $C/N  d'(N1)/2$ is also an integer! This means that if $d > 2$, then we can repeat this fact until $d$ becomes $\le 2$. This means that we only need to check for the common difference $d = 1$ and $d = 2$! Time Complexity:$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Jun '16, 15:16

@hitman333 Suppose answer exists for any given common difference d , then a must be greater than or equal to 1 and a must be an integer. Ryt? In editorial there is one equation given a=(2cn(n1)d)/(2n) when answer exists for a common difference d , then a must be integer. now replace d by d2 and find the new value of a.Let it be a' then a'=a+(n1)(you can check it out) Now a' is also integer since a is integer and (n1) is intger and it is greater than equal to 1 also. So for d4 also new a will be integer. So it basically depends on parity of d. If d is odd, u can check for d=1 and for even U can check for d=2. SO if answer exists for odd d , it will definitely exist for 1 also ,Similarly for even case. answered 22 Jun '16, 09:38

is there anything wrong in this method: ******/****** if(n==1) then "yes"; else if(n==2) { if(c>2)then "yes" else "no";} else { sum=n*(n+1)/2; if(c<sum)then "no"; else if(gcd(n,c)!=1) then yes; else n0;} answered 21 Jun '16, 23:01

could not understand why we only need to check for the common difference d=1 and d=2? answered 21 Jun '16, 23:52

My method to solve this problem was see this series a, a+d,... so total sum is na + n(n1)/2 d = C(no. of choclates) now if C % gcd(n, n(n1)/2) is 0 then we are done.. What is wrong in this solution? answered 22 Jun '16, 11:06
