Optimizing a program to solve ax + by = c with positive integers
I am writing a program that for any given natural numbers a <b <c will output YES if there is a solution for ax + by = c where x and y are also positive integers (x, y> 0) or NO if not there is a solution. Keep in mind that I need to work with large numbers.
The approach I take to solve this problem is that I subtract b from c and check if that number is divisible by.
Here's my code:
#include <stdio.h>
#include <stdlib.h>
int main(){
unsigned long long int a, b, c;
scanf("%I64u %I64u %I64u", &a, &b, &c);
while(c>=a+b){ //if c becomes less than a+b, than there no sollution
c-=b;
if(c%a==0){
printf("YES");
return 0;
}
}
printf("NO");
return 0;
}
is there a more optimized way to find that ax + by = c has positive solutions? I tried reading about linear Diophantine equations, but all I found is a way to find integer solutions (but not positive ones).
source to share
My approach so far.
- Use Euclidean algorithm to find GCD (a, b)
- There are solutions (in integers) for ax + by = c if and only if GCD (a, b) divides c. No integer solutions mean positive solutions.
- use the Extended Euclidean Algorithm to solve the Diophantine equation and return NO if it gives non-positive solutions.
For comparisons, it's hard to find examples that take more than a second, but when solving thousands of random equations, the performance difference is noticeable. In this lecture there is a solution for finding the number of positive solutions to a linear Diophantine equation.
typedef unsigned long long int BigInt;
int pos_solvable(BigInt a, BigInt b, BigInt c) {
/* returns 1 if there exists x, y > 0 s.t. ax + by = c
* where 0 < a < b < c
* returns 0, otherwise
*/
BigInt gcd = a, bb = b, temp;
while (bb) { /* Euclidean Algorithm */
temp = bb;
bb = gcd % bb;
gcd = temp;
}
if (c % gcd) { /* no integer (or positive) solution */
return 0;
} else {
/* Extended Euclidean Algorithm */
BigInt s = 0, old_s = 1;
BigInt t = 1, old_t = 0;
BigInt r = b / gcd, old_r = a / gcd;
while (r > 0) {
BigInt quotient = old_r / r;
BigInt ds = quotient * s;
BigInt dt = quotient * t;
if (ds > old_s || dt > old_t)
return 0; /* will give non-positive solution */
temp = s;
s = old_s - ds;
old_s = temp;
temp = t;
t = old_t - dt;
old_t = temp;
temp = r;
r = old_r - quotient * r;
old_r = temp;
}
return 1;
}
}
source to share
Below is a comment, but too long for a comment section.
This is posted to help others delve a little deeper into this issue.
OP: Include any of your posts if you like.
What else is needed is somewhat complex a,b,c
.
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//#define LLF "%I64u"
#define LLF "%llu"
int main(void) {
unsigned long long int a, b, c, x, y, sum, c0;
// scanf(LLF LLF LLF, &a, &b, &c);
c = c0 = ULLONG_MAX;
b = 10000223;
a = 10000169;
y = 0;
sum = a + b;
time_t t0 = time(NULL);
while (c >= sum) { //if c becomes less than a+b, than there no solution
c -= b;
if (c % a == 0) {
break;
}
}
if (c % a == 0) {
y = (c0 - c) / b;
x = c / a;
printf("YES " LLF "*" LLF " + " LLF "*" LLF " = " LLF "\n", a, x, b, y, c);
} else {
printf("NO\n");
}
time_t t1 = time(NULL);
printf("time :" LLF "\n", (unsigned long long) (t1 - t0));
return 0;
}
Output
YES 10000169*1844638544065 + 10000223*4688810 = 18446697184563946985
time :0
source to share