Cod sursa(job #3340179)

Utilizator petro123Alex Ionel petro123 Data 12 februarie 2026 15:21:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.29 kb

use std::{io, fs};
use std::fs::File;
use std::io::{BufWriter, Write};

macro_rules! parse_line {
    ($iter : expr, $($t : ty),+) => {{
        let line = $iter.next().unwrap();
        let mut parts = line.split_whitespace();
        ($(parts.next().unwrap().parse::<$t>().unwrap()),+)
    }};
}

fn gcde(a : i64, b : i64, d : &mut i64, x : &mut i64, y : &mut i64)
{
    if b == 0 {
        *d = a;
        *x = 1;
        *y = 0;
        return;
    }
    let r = a % b;
    gcde(b, r, d, x, y);
    //a x= (b * (a/b) + r) x = r yy
    //ax+by=d---(a/b)*b*x+rx+by=d---b((a/b)x+y)+rx=d
    //bxx+ryy=d
    //x =yy
    //y=xx-(a/b)x
    let (xx, yy) = (*x, *y);
    *x = yy;
    *y = xx - (a/b) * yy;
}
fn main() -> Result<(),io::Error>{
    let content = fs::read_to_string("euclid3.in")?;
    let mut writer=BufWriter::new(File::create("euclid3.out")?);
    let mut lines = content.lines();
    let testcases = parse_line!(lines, usize);
    for _ in 0..testcases {
        let (a, b, c) = parse_line!(lines, i64, i64, i64);
        let (mut x, mut y, mut d) = (0, 0, 0);
        gcde(a, b, &mut d, &mut x, &mut y);
        if c % d != 0 {
            writeln!(writer,"0 0")?;
            continue;
        }
        let multi = c/d;
        writeln!(writer, "{} {}", x * multi, y * multi)?;

    }
    Ok(())
}