// S : tags   c sym  $TAGS
// S : expect --result valid
// S : cc     -o test.bc  $CC_OPT $file
// S : verify --symbolic --solver $solver --sequential -o nofail:malloc $V_OPT test.bc

// N : V              : CC_OPT           : V_OPT : TAGS : RESULT
// V : small.5        : -DNUM=5          :       :      : valid
// V : big.10         : -DNUM=10         :       : big  : valid
// V : big.1000       : -DNUM=1000       :       : big  : valid
// V : big.100        : -DNUM=100        :       : big  : valid
// V : big.2147483647 : -DNUM=2147483647 :       : big  : valid

extern void __VERIFIER_error() __attribute__ ((__noreturn__));

/*
 * Recursive implementation of the greatest common denominator
 * using Euclid's algorithm
 *
 * Author: Jan Leike
 * Date: 2013-07-17
 *
 */

extern int __VERIFIER_nondet_int(void);

// Compute the greatest common denominator using Euclid's algorithm
int gcd(int y1, int y2) {
    if (y1 <= 0 || y2 <= 0) {
        // No non-positive input allowed
        ERROR: __VERIFIER_error();
    }
    if (y1 == y2) {
        return y1;
    }
    if (y1 > y2) {
        return gcd(y1 - y2, y2);
    }
    return gcd(y1, y2 - y1);
}

// does n divide m?
int divides(int n, int m) {
    if (m == 0) {
        return 1; // true
    }
    if (n > m) {
        return 0; // false
    }
    return divides(n, m - n);
}

int main() {
    int m = __VERIFIER_nondet_int();
    if (m <= 0 || m > NUM) {
        return 0;
    }
    int n = __VERIFIER_nondet_int();
    if (n <= 0 || n > NUM) {
        return 0;
    }
    if (m > 0 && n > 0) {
        int z = gcd(m, n);
        if (divides(z, m) == 0) {
            ERROR: __VERIFIER_error();
        } else {
            return 0;
        }
    }
}