ac-lib

A Rust library for competitive programming on AtCoder.

Features

• 🔢 Math: GCD/LCM, Prime numbers, ModInt
• 🗺️ Graph: DFS, BFS, Dijkstra, Union-Find
• 📊 Data Structures: Segment Tree, Fenwick Tree

Installation

Add this to your Cargo.toml:

[dependencies]
ac-lib = "0.1.0"

Usage

Math

use ac_lib::math::{gcd, is_prime, ModInt};

// GCD
let result = gcd(48, 18);
println!("{}", result); // 6

// Prime check
println!("{}", is_prime(17)); // true

// Modular arithmetic
let a = ModInt::new(1000000000, 1000000007);
let b = ModInt::new(1000000000, 1000000007);
let c = a.add(&b);
println!("{}", c.value()); // 1999999993

Graph

use ac_lib::graph::{dfs, bfs, dijkstra, Edge, UnionFind};

// DFS
let graph = vec![vec![1, 2], vec![0, 3], vec![0], vec![1]];
let mut visited = vec![false; 4];
let order = dfs(&graph, 0, &mut visited);

// Union-Find
let mut uf = UnionFind::new(5);
uf.union(0, 1);
uf.union(1, 2);
assert!(uf.connected(0, 2));
assert_eq!(uf.size(0), 3);

Data Structures

use ac_lib::structure::{SegmentTree, FenwickTree};

// Segment Tree
let arr = vec![1, 3, 5, 7, 9];
let mut segtree = SegmentTree::new(&arr);
println!("{}", segtree.query(1, 4)); // 15

// Fenwick Tree
let mut ft = FenwickTree::from_vec(&arr);
println!("{}", ft.range_sum(1, 3)); // 15

Testing

cargo test
Or generate locally:

```bash
cargo doc --open

Testing

cargo test

License

This project is licensed under the MIT License - see the LICENSE file for details.

Contributing

Issues and Pull Requests are welcome!