1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
use std::io;
use std::io::Write;
fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
if a == 0 {
return (b, 0, 1);
}
let p = egcd(b % a, a);
let d = p.0;
let x1 = p.1;
let y1 = p.2;
let x = y1 - (b / a) * x1;
let y = x1;
return (d, x, y);
}
fn main() -> io::Result<()> {
let stdin = io::stdin();
print!("Введите модуль m: ");
io::stdout().flush().unwrap();
let mut m = String::new();
stdin.read_line(&mut m)?;
let mut m = m.trim_end().parse::<i64>().unwrap();
print!("Введите a: ");
io::stdout().flush().unwrap();
let mut a = String::new();
stdin.read_line(&mut a)?;
let mut a = a.trim_end().parse::<i64>().unwrap() % m;
print!("Введите b: ");
io::stdout().flush().unwrap();
let mut b = String::new();
stdin.read_line(&mut b)?;
let mut b = b.trim_end().parse::<i64>().unwrap() % m;
let (d, _, _) = egcd(a, m);
if b % d != 0 {
println!("Сравнение не имеет решений");
} else {
println!("Сравнение имеет {d} решений");
a /= d;
b /= d;
m /= d;
let (_, x, _) = egcd(a, m);
let mut x0 = (x * b) % m;
if x0 < 0 {
x0 = m + x0;
}
for i in 0..d {
print!("{} ", x0 + m * i);
}
println!("");
}
return Ok(());
}
|
