Dreamoon And Sums

Review

Summary

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.

1. 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.

2. 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.

3. 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.

4. $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.

5. The definition of nice was particularly constructed by the authors to make the problem solvable. In general, it's good to focus on the structure of the problem in order to find observations. In this case, we focused on the "divisibility", including the relationship between the "quotient" $q$ and the "remainder" $r$.

6. In many "math" problems, the end-result is to find a nice formula. In general, writing down observations, variable names, equations and facts can make it easier to find the answer in the end. In this problem, we specifically wrote down:

7. $x = qb + r$

8. $q = kr$

9. $1 \leq k \leq a$ and $1 \leq r \leq b-1$

10. the summation formula and its derivation

The only time you shouldn't write everything down is when you are an International Grandmaster and you can solve this problem in a couple minutes! (Maybe even the International Grandmasters still spend some time to write down their formulas.) Otherwise, writing down facts helps to ease the load on your brain, and also makes it very easy to see patterns and formulas. 3. In this problem we were asked to find the sum of nice numbers. Instead we started by focusing on the properties of the nice numbers themselves, and this quickly led to a formula about the sum. 4. Transforming the variable $x$ into the pair of variables $(r,k)$ was a useful idea. We did not know right away that it would be useful, but it allowed us to write down the formula in a nice way in the end. 5. The last part of the problem was to simplify the formula we came up with. Once we found it in terms of $a$ and $b$, we were done. 6. This problem can be really easy if you have experience with mathematics, algebra and formulas. It also helps to be able to classify problems. When I read this problem, my initial observations pointed me in the right direction because I expected to look for a formula, since it was a "Math" problem. Problem-solving experience such as this can speed up the process as well (for example, see the Problem Classification section below)

• 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.

• Mathematics / Formulas and Proofs / Algebra and Simplification

• Combinatorics / Counting / Summation over a Set

• Brute force

• Greedy / Observations / Exploit Structure and Conditions

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.