You Are Given Some Letters...
Contest: Educational Codeforces Round 70 (Rated for Div. 2)
Difficulty rating: 2700
Tags: binary search, implementation, math

You are given $$$a$$$ uppercase Latin letters 'A' and $$$b$$$ letters 'B'.

The period of the string is the smallest such positive integer $$$k$$$ that $$$s_i = s_{i~mod~k}$$$ ($$$0$$$-indexed) for each $$$i$$$. Note that this implies that $$$k$$$ won't always divide $$$a+b = |s|$$$.

For example, the period of string "ABAABAA" is $$$3$$$, the period of "AAAA" is $$$1$$$, and the period of "AABBB" is $$$5$$$.

Find the number of different periods over all possible strings with $$$a$$$ letters 'A' and $$$b$$$ letters 'B'.

Input format:
The first line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$) — the number of letters 'A' and 'B', respectively.

Output format:
Print the number of different periods over all possible strings with $$$a$$$ letters 'A' and $$$b$$$ letters 'B'.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
All the possible periods for the first example:

- $$$3$$$ "BBABBA"
- $$$4$$$ "BBAABB"
- $$$5$$$ "BBBAAB"
- $$$6$$$ "AABBBB"

All the possible periods for the second example:

- $$$3$$$ "BAABAABA"
- $$$5$$$ "BAABABAA"
- $$$6$$$ "BABAAABA"
- $$$7$$$ "BAABAAAB"
- $$$8$$$ "AAAAABBB"

Note that these are not the only possible strings for the given periods.

Example input:
2 4

Example output:
4

Example input:
5 3

Example output:
5

Editorial:
Let's introduce the slightly naive solution. Iterate over all values for periods and check the possibility of each one being correct.
The conditions for some period $$$k$$$ can be formulated the following way. $$$g = n / k$$$ ($$$n = a + b$$$ is the total length of the string) is the number of full periods of length $$$k$$$. Let's find at least one such pair $$$cnt_a$$$ and $$$cnt_b$$$ such that $$$cnt_a + cnt_b = x$$$ and the remainder part of the string can be filled with $$$a - cnt_a \cdot g$$$ letters 'A' and $$$b - cnt_b \cdot g$$$ letters 'B'. By easy construction one can deduce that the conditions of $$$a - cnt_a \cdot g \le cnt_a$$$ and $$$b - cnt_b \cdot g \le cnt_b$$$ are enough. Thus $$$cnt_a$$$ should be greater or equal to $$$\frac{a}{g + 1}$$$ and $$$cnt_b \ge \frac{b}{g + 1}$$$.
In order to move to the faster solution one should also remember that both remainder parts $$$a - cnt_a \cdot g$$$ and $$$b - cnt_b \cdot g$$$ should be non-negative.
Let's learn how to solve the problem for the whole range of lengths which all have the number of full periods equal to the same value $$$g$$$. Let this range be $$$[l; r]$$$. From the aforementioned formulas one can notice that the restrictions on both $$$cnt_a$$$ and $$$cnt_b$$$ don't depend on the length itself but only on value of $$$g$$$. To be more specific:
$$$$$$\frac{a}{g + 1} \le cnt_a \le \frac{a}{g}$$$$$$ $$$$$$\frac{b}{g + 1} \le cnt_b \le \frac{b}{g}$$$$$$
The lowest and the highest values for $$$cnt_a$$$ and $$$cnt_b$$$ will be the following:
$$$$$$a_{low} = \lceil \frac{a}{g + 1} \rceil$$$$$$ $$$$$$a_{high} = \lfloor \frac{a}{g} \rfloor$$$$$$ $$$$$$b_{low} = \lceil \frac{b}{g + 1} \rceil$$$$$$ $$$$$$b_{high} = \lfloor \frac{b}{g} \rfloor$$$$$$
It is claimed that every value between $$$a_{low} + b_{low}$$$ and $$$a_{high} + b_{high}$$$ exists if the values are valid ($$$a_{low} \le a_{high}$$$ and $$$b_{low} \le b_{high}$$$).
The full proof about the given conditions being sufficient and the existence of every value on that range is left to the reader. Some kind of a hint might be the suggestion to check how the inequalities change on the transition from some period $$$k$$$ to $$$k + 1$$$.
Restrict the values by $$$l$$$ and $$$r$$$ to count each answer on exactly one range of lengths. Finally, the value of $$$min(r, a_{high} + b_{high}) - max(l, a_{low} + b_{low}) + 1$$$ is added to the answer.
The number of ranges with the same $$$g$$$ is $$$O(\sqrt n)$$$.
Overall complexity: $$$O(\sqrt n)$$$.