Maths Equation DSA Problem Solution

Posted by admin August 2, 2023
Maths Equation Even Numbers DSA Problem Solution
Maths Equation Even Numbers DSA Problem Solution

In this post, we are going to solve Maths Equation DSA Problem from Tiktok Singapore, Online Assessments conducted on Septemeber,2022. Let’s have a look at the problem statement first and then try to solve the problem.

Maths Equation DSA Problem Statement

Ram is having a maths exam tomorrow but today he is stuck in a problem that was related to maths equations. So he needs your help to solve the equation. Below is the equation that Ram is facing a problem to solve.

(A∗X)%N=R 

Help Ram to solve this equation by finding the minimum value of X. You are given A, R, N or print -1 if no answer exists.

Input

The first line of the test case contains a three integer A, R, N (

1≤A≤R≤N≤1018) — the integer value of the equation.

Output

For each test case print the minimum value of X which satisfies the equation If no such solution exists print -1.

Examples
Input
15 9 18
Output
3
Input
15 9 25
Output
-1

Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mid(l, r) (l + (r - l) / 2)
#define int long long
#define mod 1000000007
constexpr int MOD = 998244353;

int EEA( int a, int b,int& x, int& y)
{
if (b == 0) {
x = 1;
y = 0;
return a;
}
else {

int x1, y1;
int gcd= EEA(b, a % b, x1, y1);
x = y1;
y = x1 - floor(a / b) * y1;
return gcd;
}
}

void linear_congruence(int A, int B, int N)
{
A = A % N;
B = B % N;
int u = 0, v = 0;
int d = EEA(A, N, u, v);

// No solution exists
if (B % d != 0)
{
cout << -1 << endl;
return;
}

int x0 = (u * (B / d)) % N;
if (x0 < 0)
x0 += N;

vector<int>ans;
for (int i = 0; i <= d - 1; i++)
ans.push_back( (x0 + i * (N / d)) % N);

sort(ans.begin(),ans.end());
cout<<ans[0]<<"\n";

}
int32_t main()
{
int a, b, n;
cin >> a >> b >> n;
linear_congruence(a, b, n);
}