#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::Read; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok().unwrap(); ret } fn get_word() -> String { let stdin = std::io::stdin(); let mut stdin=stdin.lock(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get() -> T { get_word().parse().ok().unwrap() } // DP table indexed by {floor(n / i) | 1 <= i <= n}. // Verified by: https://atcoder.jp/contests/abc239/submissions/29553511 type K = i64; type V = i64; struct QuoDP { // stores dp[n], dp[n/2], ..., dp[n/b]. dp_big: Vec, dp: Vec, n: K, b: K, } impl QuoDP { pub fn new(n: K, b: K) -> Self { let dp_big = vec![0.into(); b as usize + 1]; let dp = vec![0.into(); (n / b) as usize]; QuoDP { dp_big: dp_big, dp: dp, n: n, b: b, } } #[allow(unused)] pub fn keys(&self) -> Vec { (1..self.n / self.b).chain((1..=self.b).rev().map(|x| self.n / x)).collect() } // pos should be of form floor(n / ???). pub fn upd(&mut self, pos: K, f: F) where F: Fn(V) -> V { if pos >= self.n / self.b { let idx = self.n / pos; debug_assert_eq!(pos, self.n / idx); self.dp_big[idx as usize] = f(self.dp_big[idx as usize]); return; } let idx = pos as usize; self.dp[idx] = f(self.dp[idx]); } pub fn get(&self, pos: K) -> V { if pos >= self.n / self.b { let idx = self.n / pos; debug_assert_eq!(pos, self.n / idx); return self.dp_big[idx as usize]; } let idx = pos as usize; self.dp[idx] } #[allow(unused)] pub fn init(&mut self, f: F) where F: Fn(K) -> V { self.upd_all(|k, _| f(k)); } pub fn upd_all(&mut self, f: F) where F: Fn(K, V) -> V { for i in 0..self.dp.len() { self.dp[i] = f(i as K, self.dp[i]); } for i in (1..self.dp_big.len()).rev() { self.dp_big[i] = f(self.n / i as K, self.dp_big[i]); } } } impl std::fmt::Debug for QuoDP { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { for i in 0..self.dp.len() { writeln!(f, "{}: {}", i, self.dp[i])?; } for i in (1..self.dp_big.len()).rev() { writeln!(f, "{}: {}", self.n / i as K, self.dp_big[i])?; } Ok(()) } } fn main() { let a: i64 = get(); let b: i64 = get(); let n: i64 = get(); let inf = a * (n - 1) * b; let mut sqn = 0; while sqn * sqn <= n { sqn += 1; } sqn -= 1; let mut dp = QuoDP::new(n, sqn); let keys = dp.keys(); for pos in keys { let mut x = 1; while x * x <= pos { x += 1; } x -= 1; let mut tmp = inf; for j in 2..=x { tmp = min(tmp, dp.get(pos / j) + a + (j - 1) * b); } for j in max(1, pos / n)..pos / x { let l = pos / (j + 1); let r = min(n, pos / j); if l < r { tmp = min(tmp, dp.get(j) + a + l * b); } } dp.upd(pos, |_| tmp); } println!("{}", dp.get(n)); }