Blue Bridge Cup_ Diophantine equation

a*x+b*y=c
d=gcd( a,b );
if( c%d==0 )
{
    x=x0+b/d*n;
    y=y0-a/d*n;
}

01  Find the grid point between two points of a line segment 

    ( y2-y1 )*x+( x1-x2 )*y=y2*x1-y1*x2;
    a=y2-y1;
    b=x1-x2;
    c=y2*x1-y1*x2;
    d=gcd( a,b );

    x1 < x < x2
    x1 < x1+b/d*n < x2
    -d < n < 0

    cnt=d-1;

02 pick  Theorem  s=j/2+k-1;

     Cited example :
         A closed polygon on a two-dimensional plane is given , The vertices of a polygon are all lattice points .
         Please calculate the number of grid points on the polygon boundary  j, Number of internal grid points  k, And the area of the polygon  s

03  extended euclidean algorithm _ Sum of special solutions gcd

    typedef long long LL;
    LL extend_gcd( LL a,LL b,LL& x,LL& y )
    {
        if( b==0 ) { x=1; y=0; return a; }
        LL d=extend_gcd( b,a%b,y,x );
        y-=a/b*x;
        return d;
    }

    01
        a*x0+b*y0=gcd(a,b)          (1)
        b*x1+(a%b)*y1=gcd(b,a%b)    (2)
        gcd(a,b)=gcd(b,a%b)         (3)

        (1)(2)(3) ==> a*x0+b*y0=b*x1+(a%b)*y1   (4)

        (a%b)*y1=(a-a/b*b)*y1                   (5)

        (4)(5) ==> a*x0+b*y0=b*x1+(a-a/b*b)*y1

        a*x0 b*y0
        a*y1 b*x1+(-a/b*b)*y1

         Contrast coefficient  ==> x0=y1 y0=x1-(a/b)*y1
    02 
        a*x+b*y=c
        extend_gcd() ==> x0,y0,d
        tt=c/d;
        x=x0*tt+b/d*n;
        y=y0*tt-a/d*n;