Submission details
Task:Finding inverse
Sender:aalto26kh_033
Submission time:2026-11-11 18:34:26 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#8ACCEPTED0.00 sdetails
#90.00 sdetails
#100.00 sdetails
#11ACCEPTED0.00 sdetails
#120.00 sdetails
#130.00 sdetails
#14ACCEPTED0.00 sdetails

Compiler report

input/code.cpp: In function 'bool coprime(int, int)':
input/code.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (i1<fact1.size() && i2<fact2.size()){
      |            ~~^~~~~~~~~~~~~
input/code.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (i1<fact1.size() && i2<fact2.size()){
      |                               ~~^~~~~~~~~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define REP(i,a,b) for (ll i=a;i<=b;i++)

vector<int> factorization(int n){
    vector<int> ret;
    while (n>=2){
        int i=2;
        for (;i<=floor(sqrt(n));i++){
            if (n%i){
                ret.push_back(i);
                n/=i;
                break;
            }
        }
        if (i>floor(sqrt(n))){
            ret.push_back(n);
            n=1;
        }
    }
    return ret;
}

bool coprime(int n1, int n2){
    auto fact1 = factorization(n1);
    auto fact2 = factorization(n2);

    int i1=0, i2=0;

    while (i1<fact1.size() && i2<fact2.size()){
        if (fact1[i1]==fact2[i2]){
            return false;
        } else if (fact1[i1]<fact2[i2]){
            i1++;
        } else {
            i2++;
        }
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, m;
    cin >> a >> m;

    if (!coprime(a, m)){
        cout << "-1\n"; 
    } else {
        cout << (int) pow(a, m-2)%m << '\n';
    }


    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
6 7

correct output
6

user output
6

Test 2

Verdict:

input
0 7

correct output
-1

user output
0

Test 3

Verdict:

input
5 78

correct output
47

user output
-50

Test 4

Verdict:

input
89 99

correct output
89

user output
-1

Test 5

Verdict:

input
0 61

correct output
-1

user output
0

Test 6

Verdict:

input
897 947

correct output
625

user output
-1

Test 7

Verdict:

input
419 538

correct output
217

user output
-1

Test 8

Verdict: ACCEPTED

input
32 938

correct output
-1

user output
-1

Test 9

Verdict:

input
184120 505187

correct output
438779

user output
-1

Test 10

Verdict:

input
264601 885661

correct output
360221

user output
-1

Test 11

Verdict: ACCEPTED

input
40310 590135

correct output
-1

user output
-1

Test 12

Verdict:

input
202254499 577081420

correct output
128866679

user output
-1

Test 13

Verdict:

input
539836073 888851205

correct output
797044652

user output
-1

Test 14

Verdict: ACCEPTED

input
697847215 756971670

correct output
-1

user output
-1