| Task: | Finding inverse |
| Sender: | aalto26kh_012 |
| Submission time: | 2026-11-15 16:14:37 +0200 |
| Language: | Rust (2021) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | ACCEPTED | 0.00 s | details |
| #4 | ACCEPTED | 0.00 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
Code
#![allow(unused)]
use std::collections::*;
use std::io;
fn take_tuple() -> (usize, usize) {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let mut it = input
.trim()
.split_whitespace()
.map(|x| x.parse::<usize>().unwrap());
(it.next().unwrap(), it.next().unwrap())
}
fn prime(n: usize) -> bool {
if n < 2 {
return false;
}
let mut x = 2usize;
while x * x <= n {
if n % x == 0 {
return false;
}
x += 1;
}
return true;
}
fn factors(mut n: usize) -> Vec<usize> {
let mut f: Vec<usize> = Vec::new();
let mut x = 2;
while x * x <= n {
while n % x == 0 {
f.push(x);
n /= x;
}
x += 1;
}
if n > 1 {
f.push(n);
}
f
}
fn power(x: usize, n: usize, m: usize) -> usize {
if n == 0 {
return 1usize;
}
let mut u = power(x, n / 2, m);
u = (u * u) % m;
if n % 2 == 1 {
u = (u * x) % m;
}
u
}
fn eulers_totient(mut n: usize) -> usize {
let f = factors(n);
let mut e = f[0];
let mut l = f[0];
for i in 1..f.len() {
if f[i] == l {
e *= f[i];
} else {
e *= f[i] * (f[i]-1);
l = i;
}
}
e
}
fn gcd(a: usize, b: usize) -> usize {
if b == 0 { return a; }
return gcd(b, a%b);
}
fn main() {
let (a, m) = take_tuple();
if gcd(a, m) != 1 {
println!("-1");
return;
}
let mut euler;
if prime(m) {
euler = m - 1;
} else {
euler = eulers_totient(m);
}
println!("{}", power(a, euler - 1, m));
}
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 |
