WA for testcase 10 51 5 4, help to point out mistake

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define li long int
#define ull unsigned long long
#define lli long long int
#define nL “\n”
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define a first
#define b second
#define vi vector
#define all(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define f(i, n) for(i=0; i<n; i++)
#define F(i, k, n) for(i=k; i<n; i++)
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define MOD 1000000007

ll GCD(ll a, ll b)
{
return (b == 0) ? a : GCD(b, a % b);
}

ll x, y, z;
ll gcd;

void extEucludian(ll a, ll b)
{
//base case
if (b == 0)
{
x = 1;
y = 0;
gcd = a;
return;
}
// recursive part
extEucludian(b, a % b);
ll cur_x = y;
ll cur_y = x - (a / b) * y;

x = cur_x;
y = cur_y;

}

void DioPhantineEq(ll w, ll d, ll p, ll n)
{
ll g = GCD(w, d);

if ((p % g) != 0)
{
	// cout << "No Solution Exist";
	cout << -1;
	return;
}

extEucludian(w, d);

ll k = p / g;

x = k * x;
y = k * y;
z = (n - x - y);

if (z > 0)
{
	cout << x << " " << y << " " << z <<  nL;
	return;
}

for (int t = 1; t < n; t++)     // if z negative
{
	ll temp_x = x + (d / g) * t;
	ll temp_y = y - (w / g) * t;
	ll temp_z = (n - temp_x - temp_y);

	if (temp_z > 0)
	{
		x = temp_x;
		y = temp_y;
		z = temp_z;
		break;
	}
}

cout << x << " " << y << " " << z <<  nL;  // one such solu using Ext Eucl.
return;

}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

ll n, p, w, d;
cin >> n >> p >> w >> d;

// wx + dy = p => eq solu

DioPhantineEq(w, d, p, n);

return 0;

}

Hello @devang_11912089,

You didn’t add this condition w*n < p, in this case, the answer is always -1.
Secondly, your logic is wrong you are iterating t from 1 to n ( n <= 1e12 ) which will give you time limit exceeded.

1 Like

ok,
but t loop will break when we get z as positive

@devang_11912089,

If z becomes positive at n-1 then you are iterating ~ almost n times

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

can you please explain this code discussed in video part

func ->

int modInverse(int a, int m)
{
if (m == 1) return 0;
int m0 = m, y = 0, x = 1;
while (a > 1)
{
int q = a / m, t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += m0;

return x;

}

Hello @devang_11912089,
This is Modulo Multiplicative Inverse that uses Extended Euclidean Algorithm. You can find more about this on, Link.

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.