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(());
}