CSES - Aalto Competitive Programming 2024 - wk11 - Homework - Results
Submission details
Task:Finding inverse
Sender:Rasse
Submission time:2024-11-14 14:03:53 +0200
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <cmath>
#include <functional>
#include <type_traits>
#include <fstream>
#include <bitset>
#include <complex>
#include <iomanip>
#define int long long
using namespace std;
#define cross(x, y) (((x)*conj(y)).imag())
#define sign(v) ((0 < (v)) - ((v) < 0))
int p(int a, int b, int m)
{
if (b == 0) return 1;
else if (b % 2 == 0) { int r = p(a, b/2, m); return (r*r) % m; }
else return (p(a, b-1, m)*a) % m;
}
int gdc(int a, int b)
{
if (b == 0) return a;
return gdc(b, a%b);
}
void solve()
{
int a, m;
cin >> a >> m;
if (gdc(a, m) != 1)
{
cout << -1;
return;
}
unordered_map<int, int> factors;
int num = m;
for (int i = 2; i*i <= num; i++)
{
while (num % i == 0)
{
factors[i]++;
num /= i;
}
}
if (num > 1)
factors[num]++;
// Calc phi
int phi = 1;
for (auto kv : factors)
phi *= p(kv.first, kv.second-1, m) * (kv.first - 1);
cout << p(a, phi-1, m) << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cout.precision(25);
//setprecision(10);
//cin.tie(0);
int t = 1;
//cin >> t;
//ifstream f("testcase.txt");
//cin.rdbuf(f.rdbuf());
for (int i = 0; i < t; i++)
{
solve();
cout.flush();
}
}

Test details

Test 1

Verdict: ACCEPTED

input
6 7

correct output
6

user output
6

Test 2

Verdict: ACCEPTED

input
0 7

correct output
-1

user output
-1

Test 3

Verdict: ACCEPTED

input
5 78

correct output
47

user output
47

Test 4

Verdict: ACCEPTED

input
89 99

correct output
89

user output
89

Test 5

Verdict: ACCEPTED

input
0 61

correct output
-1

user output
-1

Test 6

Verdict: ACCEPTED

input
897 947

correct output
625

user output
625

Test 7

Verdict: ACCEPTED

input
419 538

correct output
217

user output
217

Test 8

Verdict: ACCEPTED

input
32 938

correct output
-1

user output
-1

Test 9

Verdict: ACCEPTED

input
184120 505187

correct output
438779

user output
438779

Test 10

Verdict: ACCEPTED

input
264601 885661

correct output
360221

user output
360221

Test 11

Verdict: ACCEPTED

input
40310 590135

correct output
-1

user output
-1

Test 12

Verdict: ACCEPTED

input
202254499 577081420

correct output
128866679

user output
128866679

Test 13

Verdict: ACCEPTED

input
539836073 888851205

correct output
797044652

user output
797044652

Test 14

Verdict: ACCEPTED

input
697847215 756971670

correct output
-1

user output
-1