/**
 * diophantine equation solver (of two variables)
 * 
 * Given ax + by = s,
 * usage: ./diophantine a b s
 *
 * This program will spit out the first solution it finds to equation formed by
 * the given parameters. It will print an error message if there are no
 * solutions.
 *
 * Compile with: gcc -o diophantine diophantine.c
 *
 * Matt Sparks, 2006-10-12
 * http://f0rked.com
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct coords {
    int x;
    int y;
} coords;

/* Find greatest common divisor.
   Parameters are two positive integers, not both zero. */
int gcd(int a, int b) {
    /* some simple error checking */
    if ((a < 0 || b < 0) || (a == 0 && b == 0)) return -1;

    /* make 'a' the maximum by swapping */
    if (a < b) {
        int t;
        t = a; a = b; b = t;
    }

    /* if either input is 0, we're done. This is the base case.
       Although, 'a' should never be zero. */
    if (b == 0) return a;
    if (a == 0) return b;

    a = a % b;
    return gcd(a,b);
}

coords solve(int a, int b, int s) {
    int g = gcd(a,b);

    /* reduce */
    a /= g;
    b /= g;
    s /= g;
    
    /* look for solutions!
       We do this by solving for y in slope-intercept form of the reduced
       equation. The form looks like:
          y = (1/b)(-a*x + s)
       We iterate through possible values of x, starting at 1, looking for a
       sum of -a*x+s that is divisible by b. We stop after the first one is
       found. */
    int t, x = 0, y;
    while(1) {
        x++;
        t = -a*x + s;
        if (t % b == 0) break;
    }

    coords sol;
    sol.x = x;
    sol.y = t / b;

    return sol;
}

int main(int argc, char **argv) {
    if (argc < 4) {
        printf("usage: %s <A> <B> <C>\n",argv[0]);
        printf("\twhere the arguments form this equation:\n");
        printf("\t\tAx + By = C\n");
        printf("This program should indicate if there is no solution.\n");
        exit(-1);
    }

    /* ax + by = s */
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    int s = atoi(argv[3]);

    /* if s is not divisible by the gcd, there is no solution. */
    if (s % gcd(a,b) > 0) {
        printf("There is no solution to %dx + %dy = %d.\n",a,b,s);
        exit(0);
    }

    coords sol = solve(a,b,s);

    printf("solution: %d(%d) + %d(%d) = %d\n", a, sol.x, b, sol.y, s);
}