Finding inverse

#include <iostream>

typedef long long ll;

ll euclidExtended(ll a, ll b, ll &x, ll &y) {
  if (b==0) {
   y = 0, x = 1;
   return a; 
  }
  ll gcd = euclidExtended(b, a % b, y, x);
  y = y - a/b * x;
  return gcd;
}


int main(){
  ll a,M,x,y;
  std::cin >> a >> M;
  ll gcd = euclidExtended(a, M, x, y);
  ll ans = (x + M) % M;
  if (gcd!=1) ans=-1;
  std::cout << ans << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED