<commit_before>#[crate_type = "rlib"];

use std::{iter, vec};

pub static EXPECTED_ANSWER: &'static str = "18407904";

// [定理]
// a + b = c のとき、
// GCD(a, b) = 1 => GCD(a, c) = GCD(b, c) = 1
//
// [証明]
// まず、GCD(a, b) = 1 => GCD(a, c) = 1 を示す。
// GCD(a, b) のとき、GCD(a, c) = k > 1 であると仮定すると、
// 整数 n, m を用いて a = kn, c = km と表すことができる。
// b = c - a = km - kn = k(m, n) より、GCD(a, b) >= k となり矛盾。
// よって、GCD(a, c) = 1 である。
//
// 次に、GCD(a, b) = 1 => GCD(b, c) = 1 を示す。
// GCD(a, b) = 1 のとき、GCD(b, c) = k > 1 であると仮定すると、
// 整数 n, m を用いて b = kn, c = km と表すことができる。
// ここで、a = c - b = km - kn = k(m - n) より、 GCD(a, b) >= k となり矛盾。
// よって、GCD(b, c) = 1 である。

#[deriving(Eq)]
struct Rad(uint, ~[uint]);

fn create_rad_vec(n_limit: uint) -> ~[Rad] {
    let mut rad_vec = vec::from_fn(n_limit, |_| Rad(1, ~[]));
    for p in range(2, rad_vec.len()) {
        let Rad(n, _) = rad_vec[p];
        if n != 1 { continue }

        for np in iter::count(p, p).take_while(|&np| np < n_limit) {
            let Rad(ref mut n, ref mut facts) = rad_vec[np];
            (*n) *= p;
            facts.push(p);
        }
    }
    rad_vec
}

fn rad_has_union(&Rad(_, ref a): &Rad, &Rad(_, ref b): &Rad) -> bool {
    let mut i_a = 0;
    let mut i_b = 0;

    loop {
        if i_a >= a.len() || i_b >= b.len() { return false }
        match a[i_a].cmp(&b[i_b]) {
            Equal   => return true,
            Less    => i_a += 1,
            Greater => i_b += 1
        }
    }
}

fn abc_hits_c_sum(c_limit: uint) -> uint {
    let rad_vec = create_rad_vec(c_limit);
    let mut c_sum = 0;

    for c in range(3, c_limit) {
        let Rad(rad_c, _) = rad_vec[c];
        for a in range(1, (c + 1) / 2) {
            let b = c - a;
            let Rad(rad_a, _) = rad_vec[a];
            let Rad(rad_b, _) = rad_vec[b];
            let rad_abc = rad_a * rad_b * rad_c;
            if rad_abc >= c || (a > 1 && rad_has_union(&rad_vec[a], &rad_vec[c])) { continue; }
            c_sum += c;
        }<commit_msg>Some optimization for #127<commit_after>#[crate_type = "rlib"];

use std::{iter, vec};

pub static EXPECTED_ANSWER: &'static str = "18407904";

// [定理]
// a + b = c のとき、
// GCD(a, b) = 1 => GCD(a, c) = GCD(b, c) = 1
//
// [証明]
// まず、GCD(a, b) = 1 => GCD(a, c) = 1 を示す。
// GCD(a, b) のとき、GCD(a, c) = k > 1 であると仮定すると、
// 整数 n, m を用いて a = kn, c = km と表すことができる。
// b = c - a = km - kn = k(m, n) より、GCD(a, b) >= k となり矛盾。
// よって、GCD(a, c) = 1 である。
//
// 次に、GCD(a, b) = 1 => GCD(b, c) = 1 を示す。
// GCD(a, b) = 1 のとき、GCD(b, c) = k > 1 であると仮定すると、
// 整数 n, m を用いて b = kn, c = km と表すことができる。
// ここで、a = c - b = km - kn = k(m - n) より、 GCD(a, b) >= k となり矛盾。
// よって、GCD(b, c) = 1 である。

#[deriving(Eq)]
struct Rad(uint, ~[uint]);

fn create_rad_vec(n_limit: uint) -> ~[Rad] {
    let mut rad_vec = vec::from_fn(n_limit, |_| Rad(1, ~[]));
    for p in range(2, rad_vec.len()) {
        let Rad(n, _) = rad_vec[p];
        if n != 1 { continue }

        for np in iter::count(p, p).take_while(|&np| np < n_limit) {
            let Rad(ref mut n, ref mut facts) = rad_vec[np];
            (*n) *= p;
            facts.push(p);
        }
    }
    rad_vec
}

fn rad_has_union(&Rad(_, ref a): &Rad, &Rad(_, ref b): &Rad) -> bool {
    let mut i_a = 0;
    let mut i_b = 0;

    loop {
        if i_a >= a.len() || i_b >= b.len() { return false }
        match a[i_a].cmp(&b[i_b]) {
            Equal   => return true,
            Less    => i_a += 1,
            Greater => i_b += 1
        }
    }
}

fn abc_hits_c_sum(c_limit: uint) -> uint {
    let rad_vec = create_rad_vec(c_limit);
    let mut c_sum = 0;

    for c in range(3, c_limit) {
        let Rad(rad_c, _) = rad_vec[c];
        if rad_c == c { continue } // if rad(c) == c, rad(ab) must be 1. this doesn't satisfy condition 2.

        // if a == 1, GCD(a, b) == GCD(b, c) == GCD(c, a) == 1 is always satisfied.
        {
            let Rad(rad_b, _) = rad_vec[c - 1];
            if rad_b * rad_c < c { c_sum += c; }
        }

        // if c is even, a and b must be odd
        if c.is_even() {
            for a in iter::range_step(3, (c + 1) / 2, 2) {
                let b = c - a;
                let Rad(rad_a, _) = rad_vec[a];
                let Rad(rad_b, _) = rad_vec[b];
                let rad_abc = rad_a * rad_b * rad_c;
                if rad_abc >= c || rad_has_union(&rad_vec[a], &rad_vec[c]) { continue; }
                c_sum += c;
            }
        } else {
            for a in range(2, (c + 1) / 2) {
                let b = c - a;
                let Rad(rad_a, _) = rad_vec[a];
                let Rad(rad_b, _) = rad_vec[b];
                let rad_abc = rad_a * rad_b * rad_c;
                if rad_abc >= c || rad_has_union(&rad_vec[a], &rad_vec[c]) { continue; }
                c_sum += c;
            }
        }
{'fraction_non_alphanumeric': 0.19041640510567065, 'fraction_numerical': 0.015693659761456372, 'mean_word_length': 1.7361190612478534, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5168011', 'n_tokens_mistral': 2291, 'n_tokens_neox': 2181, 'n_words': 554}