# Maths Equation 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.

$\left(A\ast X\right)\mathrm{%}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\le A\le R\le N\le {10}^{1}8$$1 \le A \le R \le N \le 10^18$) — 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);
}