atcoder_arith_util.rs

mod arith_util{
    pub fn div(a: i64, b: i64) -> (i64, i64){
        let q = a/b;
        let r = a % b;
        if r < 0{
            return (q-1, r + b);
        }else{
            return (q, r);
        }
    }

    pub fn div_up(a: i64, b: i64) -> i64{
        let (q, r) = div(a, b);
        if r == 0{
            return q;
        }else{
            return q + 1;
        }
    }

    #[test]
    fn test_div(){
        assert_eq!(div(7, 2), (3, 1));
        assert_eq!(div(-7, 2), (-4, 1));
        assert_eq!(div(-8, 2), (-4, 0));
        assert_eq!(div_up(6, 2), 3);
        assert_eq!(div_up(7, 2), 4);
        assert_eq!(div_up(-7, 2), -3);
    }

    pub fn extgcd(a: i64, b: i64) -> ((i64, i64), i64){
        if a == 0 && b == 0{
            return ((0, 0), 0);
        }
        if a < 0{
            let ((x, y), g) = extgcd(-a, b);
            return ((-x, y), g);
        }
        if b < 0{
            let ((x, y), g) = extgcd(a, -b);
            return ((x, -y), g)
        }
        if a < b{
            let ((x, y), g) = extgcd(b, a);
            return ((y, x), g);
        }
        // a >= b >= 0
        if b == 0{
            return ((1, 0), a);
        }
        // a >= b > 0
        let (q, r) = div(a, b);
        let ((x1, y1), g) = extgcd(b, r);

        return ((y1, x1 - q*y1), g);
    }

    #[test]
    fn test_extgcd(){
        assert_eq!(extgcd(7, 11), ((-3, 2), 1));
        assert_eq!(extgcd(1, 1), ((0, 1), 1));
        assert_eq!(extgcd(4, 2), ((0, 1), 2));
    }

}