Dreamoon And Sums

Review

Upon looking at the problem, we notice that it will likely be a math problem. Because the numbers ($a$, $b$, and the total sum / answer) can be fairly large, we might expect that there will be some kind of nice formula that we will have to compute. However, because $a$ and $b$ can be at most $10^7$ we should also keep in mind that we might want to try some kind of brute force (where we try the numbers from 1 to $a$ or from $1$ to $b$, which should pass the 1.5 second time-limit).

So these two separate ideas (finding a mathematical formula + some kind of brute force) make up the initial observations.

Next we ask the question: "How do we find a formula?" To do this we need to exploit the structure of the problem. We need to find out "what makes a number nice" and "how does the sum of nice numbers look?" At this point, it is best to write out the information we have, and see if we can come to something that works. As a "problem-solving technique", this is when it helps to work backwards. In particular, we start by assuming we have a nice number $x$, and asking what properties of $x$ make this problem easy.

So we try this. Let $x$ be an arbitrary nice number. Since the definition of niceness depends on the "quotient" and "remainder" upon division by $b$, we will write out $x = qb + r$ where $q$ is the quotient and $r$ is the remainder ($0 \leq r \lt b$). Now, we notice that the definition of "nice", using $q$ and $r$ is exactly as follows:

where $k$ is some integer between $1$ and $a$. Rewriting this without the fractions gives us:

We can play around with the formula a bit more and we notice that, since $x = qb + r$ and $q = kr$, we can substitute this second formula into the first formula, and we get that

Now, let's stop and think. We notice that this formula for $x$ really only depends on $k$ and $r$ (since $b$ is a constant, given as input). In particular, if we know $k$ and $r$ then we know $x$. But does this work with any $k$ and $r$? Well, by definition of $r$ (being the remainder), we know that $0 \leq r \lt b$. But we also know that $r \neq 0$ (this was somewhere in the definition of "nice"). So altogether we know that

are all the possible choices of $r$. Similarly, almost by definition of "nice", we know the integer $k$ must satisfy:

And more importantly, if we pick any $k$ and $r$ that are in these ranges, then we uniquely get an $x$ by setting $x = r(kb + 1)$.

(Note: In combinatorics, this is often called a "bijection" or a "one-to-one correspondence". We can think of the set of nice $x$ values as equivalent to the set of pairs $(k,r)$, with $1 \leq k \leq a$ and $1 \leq r \leq b-1$.)

Now, we have a nice formula involving nice numbers! Let's focus on the key problem: Finding the sum of all the nice numbers. It turns out that we can solve this by writing out the formula as well, this time remembering the "one-to-one correspondence" we just found. That is:

That is, our answer is just the sum of $r(kb+1)$ over all choices of $r$ and $k$, since each of these pairs gives us a nice number.

From here, the rest is just algebra. We now want to simplify the formula we just came up with above by expanding it and then "collecting similar terms". I personally just wrote this all down on paper until I came to a nice simple formula. The derivation follows. (Beware, it may actually be easier for the reader to do the algebra independently). Here is the full derivation:

Of course, being able to do this algebra requires some basic experience with equations and algebra. We also used the fact that:

This was used a couple times in the derivation above. It comes up fairly often, so it's nice to remember this identity. You should also be familiar with factoring and dealing with "sigma" ($\sigma$) notation. Also, be careful about "off-by-one" errors! (During the contest, I almost had a bug because I accidentally wrote $b+1$ instead of $b-1$ somewhere in the formula. I found it though...)

Anyway, all-in-all, we notice that the final formula has no summations in it, and no variables except $a$ and $b$ (which are given constants). So this is enough to solve the problem; Given $a$ and $b$, we just print out the last line of that formula, and we're done! (It turns out we didn't need to use brute force!)

Note: Be careful with overflow. Since $a$ and $b$ are big, doing these multiplications will overflow a 32 bit integer. It may even overflow a 64-bit integer if you are not careful. So make sure to take everything modulo $1,000,000,007$ multiple times in that formula above. But over all, this is the key idea.

Key observations:

• If we write $x = qb+r$ where $q$ is the quotient and $0 \leq r \leq b-1$, then $x$ is nice if and only if: $r \neq 0$ and $q = kr$ (with $1 \leq k \leq a$). We found this by working backwards, and it led to a nice characterization of the nice numbers.
• There is a unique nice number $x$ corresponding to each pair of integers $(r,k)$ with $1 \leq r \leq b-1$ and $1 \leq k \leq a$. In particular, this number is: $r(kb + 1)$. This was the "bijection" that made it easy to write out the sum later.
• The final sum of all nice numbers is: $\left(\frac{b\cdot a(a+1)}{2} + a \right) \times \left(\frac{b(b-1)}{2} \right)$. We found this by writing out the formula, using the $(r,k)$ bijection we described above. With a little bit of algebra, we eventually came to this nice formula that only includes $a$ and $b$, with no other variables in it. This gives us a constant time solution.
• $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for any integer $n$. This is a basic algebraic identity related to the "Triangular Numbers". It was used a couple times when simplifying the formula.

References

Problem-solving techniques used:

Learning points:

• This problem would have been really hard if you didn't think to write out the formula. It might have also been hard if you didn't think of writing out the variable $x$ as a quotient and remainder, as $x = qb + r$. As a learning point, we recognize that writing out variables and observations can often be helpful, as long as we don't spend too much time working through the algebra.

Topics:

• Mathematics / Formulas and Proofs / Algebra and Simplification
• Combinatorics / Counting / Summation over a Set
• Brute force
• Greedy / Observations / Exploit Structure and Conditions

Related problems:

• Suppose you didn't know the identity $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$. Can you think of a linear time $\Theta(a + b)$ algorithm to solve the problem? (You can still use any of the other observations from above if you want to.)
• Let's change the definition of nice. What if a nice number $x$ is one where $div(x,b) \times mod(x,b)$ is an integer between $1$ and $a$? How would we solve this modified problem? Can we still find a nice formula for the sum of the nice numbers? What is it? If not, can we do a brute force this time? How, or why not? All-in-all, come up with some algorithm to solve this modified problem: Find the sum of all "modified" nice numbers.
• Find an identity for $1^2 + 2^2 + 3^2 + \cdots + n^2 = \ ?$ for any integer $n$.
• Codeforces Round #273 (Div. 2), Problem B - Random Teams. A bit more practice with binomial coefficients and math.