Counting Good Prefixes

For any two positive integers \(a\) and \(b\), we define the function gen_string(a,b) as follows:

# Python code
 def gen_string(a: int, b: int):
     res = ""
     ia, ib = 0, 0
     while ia + ib < a + b:
         if ia * b 
// Equivalent C++ code:
string gen_string(int64_t a, int64_t b) {
string res;
int ia = 0, ib = 0;
while (ia + ib < a + b) {
if ((__int128)ia * b <= (__int128)ib * a) {
res += '0';
ia++;
} else {
res += '1';
ib++;
}
}
return res;
}

Note that when the function terminates, \(ia=a\) and \(ib=b\). Thus, gen_string(a,b) produces a bitstring of length \(a+b\) containing exactly \(a\) zeroes and \(b\) ones.

A bitstring \(s\) (of length \(x+y\) with exactly \(x\) zeroes and \(y\) ones) is called good if there exist positive integers \(x\) and \(y\) such that \(s = gen_string(x,y)\). Given two positive integers \(A\) and \(B\) (with \(1\le A,B\le10^{18}\)), let \(S = gen_string(A,B)\). Your task is to compute the number of good prefixes of \(S\).

It turns out that \(S\) is the lower Christoffel word with slope \(B/A\) and a well known fact about Christoffel words is that the number of its Christoffel (or good) prefixes is given by

[ \text{answer} = \frac{A}{d} + \frac{B}{d} - 1, \quad \text{where } d = \gcd(A,B). ]

For example, when \(A=4\) and \(B=10\), we have \(d=2\) and the number of good prefixes is \(\frac{4}{2}+\frac{10}{2}-1 = 2+5-1=6\). The six good prefixes (together with the associated pairs \((x,y)\)) are:

x = 1 | y = 1 | gen_string(1, 1) = 01
x = 1 | y = 2 | gen_string(1, 2) = 011
x = 1 | y = 3 | gen_string(1, 3) = 0111
x = 2 | y = 5 | gen_string(2, 5) = 0111011
x = 3 | y = 7 | gen_string(3, 7) = 0111011011
x = 4 | y = 10 | gen_string(4, 10) = 01110110111011

Using the formula above, you are to compute the number of good prefixes for the given \(A\) and \(B\).

inputFormat

The input consists of a single line with two positive integers \(A\) and \(B\) (\(1 \le A, B \le 10^{18}\)).

outputFormat

Output a single integer representing the number of good prefixes of \(gen_string(A,B)\).

sample

4 10

6