help with exgcd problem

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

om1429888's blog

help with exgcd problem

By om1429888, history, 2 years ago, In English

https://mirror.codeforces.com/problemsets/acmsguru/problem/99999/106 can someone please help me solve this?

om1429888
2 years ago
6

Comments (4)

Show archived | Write comment?

islingr

2 years ago, # |

← Rev. 5 →

Note that if $$$\gcd(a, b) \not\mid c$$$, no solution exists. Otherwise, divide $$$a, b, c$$$ by this $$$\gcd$$$, now we assume $$$\gcd(a, b) = 1$$$.

Let $$$x_0, y_0$$$ be any integer solution of the equation (which can be found using Euclid's algorithm).

One can prove that all solutions of the equation must be of the form $$$(x_0 - b n, y_0 + a n)$$$ for some integer $$$n$$$.

Now, we end up with the problem of counting integer $$$n$$$ such that $$$x_1 \le x_0 - b n \le x_2$$$, $$$y_1 \le y_0 + a n \le y_2$$$.

This can be done by just getting min and max bounds on $$$n$$$ using the above inequalities. Make sure to take care of all the cases such as $$$a = 0$$$, $$$a < 0$$$, when the upper bound is less than the lower bound, etc..

→ Reply

om1429888

2 years ago, # ^ |

how to find the bounds?

→ Reply

islingr

2 years ago, # ^ |

If $$$b > 0$$$, you have

$$$x_1 \le x_0 - b n \le x_2 \iff x_0 - x_1 \ge b n \ge x_0 - x_2 \iff \frac{x_0 - x_1}{b} \ge n \ge \frac{x_0 - x_2}{b}$$$

If b < 0, the inequalities are reversed.

You similarly get another relation from the other inequality.

Take note of the fact that what I have written above is real division, not integer division.

→ Reply

YMSeah

2 years ago, # |

← Rev. 2 →

You can take reference from CP-algorithms's tutorial on Linear Diophantine Equations. They have the exact solution. There are a lot of edge cases to consider like if a == 0 or b == 0 etc, or a < 0 or b < 0.

Python Solution. Note that '//' is a floor divide in Python


def readIntArr():
    return [int(x) for x in input().split()]

def extended_gcd(a, b):
    """returns gcd(a, b), s, r s.t. a * s + b * r == gcd(a, b)"""
    s, old_s = 0, 1
    r, old_r = b, a
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    return old_r, old_s, (old_r - old_s * a) // b if b else 0

def roundup(x):
    if x == int(x):
        return int(x)
    else:
        y = int(abs(x))
        if x < 0:
            return -y
        else:
            return y + 1

def rounddown(x):
    if x == int(x):
        return int(x)
    else:
        y = int(abs(x))
        if x < 0:
            return -y - 1
        else:
            return y

def solve():
    a, b, c = readIntArr()
    x1, x2 = readIntArr()
    y1, y2 = readIntArr()
    
    c *= -1
    
    if a == 0 and b == 0:
        if c == 0:
            ans = (x2 - x1 + 1) * (y2 - y1 + 1)
        else:
            ans = 0
        print(ans)
        return
    if a == 0:
        if c % b == 0 and y1 <= c // b <= y2:
            ans = 1
        else:
            ans = 0
        print(ans)
        return
    if b == 0:
        if c % a == 0 and x1 <= c // a <= x2:
            ans = 1
        else:
            ans = 0
        print(ans)
    
    g, xg, yg = extended_gcd(a, b)
    
    if c % g != 0:
        ans = 0
        print(ans)
        return

    x0 = xg * (c // g)
    y0 = yg * (c // g)
    
    
    k = roundup((x1 - x0) / (b // g))
    xlow = x0 + k * (b // g)
    k = rounddown((x2 - x0) / (b // g))
    xhigh = x0 + k * (b // g)
    
    if xlow > xhigh:
        ans = 0
        print(ans)
        return
    
    ylow = (c - a * xlow) // b
    yhigh = (c - a * xhigh) // b
    if ylow > yhigh:
        ylow, yhigh = yhigh, ylow
    
    k = roundup((y1 - y0) / (a // g))
    ylow2 = y0 + k * (a // g)
    k = rounddown((y2 - y0) / (a // g))
    yhigh2 = y0 + k * (a // g)
    
    ylow3 = max(ylow, ylow2)
    yhigh3 = min(yhigh, yhigh2)
    
    if ylow3 > yhigh3:
        ans = 0
        print(ans)
        return
    
    ans = 1 + (yhigh3 - ylow3) // abs(a // g)
        
    print(ans)
            
solve()

→ Reply