Решение задачи №100 от UniLecs (Овощная нарезка)

vegetable_slicing.rs

extern crate num;

type Input = u32;

mod gcd_memo {
    use super::Input;
    use std::collections::HashMap;

    type GcdAcc = HashMap<(Input, Input), Input>;
    pub struct GcdMemo(GcdAcc);

    impl GcdMemo {
        pub fn new() -> Self {
            GcdMemo(GcdAcc::new())
        }

        #[inline]
        pub fn gcd(&mut self, a: Input, b: Input) -> Input {
            let (a, b) = if a > b { (a, b) } else { (b, a) };
            self.gcd_recurrent(a, b)
        }

        fn gcd_recurrent(&mut self, a: Input, b: Input) -> Input {
            if b == 0 {
                return a;
            }

            match self.0.get(&(a, b)) {
                Some(&ready_answer) => ready_answer,
                None => {
                    let answer = self.gcd(b, a % b);
                    self.0.insert((a, b), answer);
                    answer
                }
            }
        }
    }
}

#[deny(overflowing_literals)]
const BORDER: Input = 100_000;

#[derive(Debug, PartialEq, Eq)]
enum CircleLayoutError {
    OutOfBound,
}

impl gcd_memo::GcdMemo {
    fn count_circle_layouts(&mut self, circle: Input) -> Result<num::BigUint, CircleLayoutError> {
        use num::{BigUint, One, Zero};
        use std::collections::BTreeMap;
        use CircleLayoutError::*;

        if circle >= BORDER {
            return Err(OutOfBound);
        }

        let mut count_gcds = BTreeMap::new();
        for i in 1..=circle {
            *count_gcds.entry(self.gcd(circle, i)).or_insert(0u32) += 1;
        }

        let mut acc: BigUint = Zero::zero();
        let mut power: BigUint = One::one();
        let mut prev = 0;
        for (gcd, count) in count_gcds {
            power <<= (gcd - prev) as usize;
            acc += &power * count;
            prev = gcd;
        }

        Ok(acc / circle)
    }
}

#[test]
fn some_variants() {
    use gcd_memo::GcdMemo;
    use CircleLayoutError::*;

    let memo = &mut GcdMemo::new();

    assert_eq!(memo.count_circle_layouts(3), Ok(4u32.into()));
    assert_eq!(memo.count_circle_layouts(5), Ok(8u32.into()));
    assert_eq!(memo.count_circle_layouts(10), Ok(108u32.into()));

    assert_eq!(memo.count_circle_layouts(BORDER), Err(OutOfBound));
    assert_eq!(
        memo.count_circle_layouts(9_999),
        Ok("9976313215725364460864797293147240143131797339164878762136\
            25837510222963807478079403938478049614691364102966767837239\
            93757158172564325338121781107771258745663845034737442716905\
            51678443477377685528827926251721827954049709201229175260280\
            56548959377182122736768418742336930774740366567735188992594\
            38728434783804505933812753480581857543889316197734116102418\
            71345022317052086627103090675181785724393177409719162645749\
            30688039345982625075898643095380904760177844062688745404697\
            60377212568258505522135470843573223720700948125675477704810\
            45203610164705593401221262144865929336559606377870077735098\
            78884368507592455326319361343097164485436999663856426990585\
            84230643679678061595341161629804599406294181287143046269784\
            11907811481960293865231810211731000271189438344458873961048\
            70858685481528742686775227165728658282868667163332341297554\
            36986179897196283848692552950052440815363111866635391110127\
            58185920057826261424374815486751598080591095131994632971554\
            68642895839793300443839817526781408461739021497722575010913\
            65388568894488660175507846970287300954035768108787091450841\
            19403294031639745162896712977814670820101911897788345581385\
            44989527111207993574769566005241073271892909469540830321457\
            63862770966728838991896189003333637405584747664904706884564\
            31780006787051097165863781245029933797091335779565363096408\
            44293343432628136608569083471268833681361275334039813251639\
            33776623105763181556060019081027912720122624297651418057185\
            06370296831984900976675959200256078564506902566668374607333\
            43054191181990963621872802827648845422215962883327096408958\
            31075599263711060884321625271900037500145097370255532375403\
            21940801236019301041596082531920412176699761401642700733947\
            57703299261651220164665857205194215856562697987106651017299\
            68591788254554351320850183511991856483067222732680642975156\
            80573751910805205973510759794089697707731481975055349397747\
            22701415391162167648268903669532359741073491141925909767924\
            56291507267730997537384551673010545222119530554941960396511\
            93242785905765776916705307449622650468410290347155234269132\
            43965645478522769509464480889878692493259494443816554759836\
            41993030228962863136193775334543066708495364901293362905247\
            70209053911267652004419224575333326827076128757666144019948\
            49838930913590259743988397205935868822762401398692681016174\
            64891391698420310339515988067446961198762384631768064802087\
            99293907572416136345342715336916517810441182905940152721374\
            23000194980002670666540236907869707803745627243026697838926\
            53378471928085793575089118318440647107873040425494815338238\
            89281654681665515903505754976285248252298170981131322169775\
            49571071646642902757899569784841314387983079572883490461877\
            19560866877692819092192712454051699417810946461346856778938\
            75536979714259513698255255329961628193492272213770545062379\
            76888756426236765644542121981967393027229271367478715707550\
            03442062762140783791723823544676905765561259764934215680220\
            54269590085880387123089353200055846589305212219552588302053\
            95973749662026264322361961626682856309243597352509707584157\
            528050170217872885136073960832418574238154958664732257440"
            .parse()
            .unwrap())
    );
}

Playground: http://play.rust-lang.org/?gist=d87772b20080b4b869f1a77a4c31dec9&version=stable&mode=debug