package yukicoder; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigInteger; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.List; import java.util.Queue; import java.util.Random; import java.util.stream.Collectors; public class N555 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(), c = ni(), v = ni(); // minimize c*x+v(a[0]+a[1]+...+a[x-1]) // subject to (a[0]+1)*(a[1]+1)*...*(a[x-1]+1) >= n (... => maximize) long min = Long.MAX_VALUE; for(int x = 1;x <= 20;x++){ long under = (long)(Math.pow(n, 1./x)+1e-10); // log(under)*A + log(under+1)*(x-A) >= log n // A <= (log n - xlog(under+1))/(log(under)-log(under+1)) long amin = (long)((Math.log(n)-x*Math.log(under+1))/(Math.log(under) - Math.log(under+1))+1e-10); assert 0 <= amin; assert amin <= x; assert Math.pow(under, amin) * Math.pow(under+1, x-amin) >= n; // tr(x, under, amin, (long)c*x+v*(amin*(under-1)+(x-amin)*(under))); min = Math.min(min, (long)c*x+v*(amin*(under-1)+(x-amin)*(under))); } out.println(min); } public static List factorize(long[] f, int mod) { List faps = doSquareFreeFactorization(f, mod); List nfaps = faps.stream().flatMap(fap -> { List res = doDistinctDegreeFactorization(fap.factor, mod); for(FactorAndPower resfap : res)resfap.power = fap.power; return res.stream(); }).collect(Collectors.toList()); List nnfaps = nfaps.stream().flatMap(fap -> { List res = doCantorZassenhaus(fap, mod, new Random()); return res.stream(); }).collect(Collectors.toList()); return nnfaps; } public static class FactorAndPower { long[] factor; long power; int degree; public FactorAndPower(long[] factor, long power) { this.factor = factor; this.power = power; } public FactorAndPower(long[] factor, long power, int degree) { this.factor = factor; this.power = power; this.degree = degree; } @Override public String toString() { return "FactorAndPower [factor=" + Arrays.toString(factor) + ", power=" + power + ", degree=" + degree + "]"; } } /** * f -> f_1^1*f_2^2*f_3^3*... (% mod) * @param f * @param mod * @return */ public static List doSquareFreeFactorization(long[] f, int mod) { int i = 1; List R = new ArrayList<>(); long[] g = d(f, mod); if(g.length > 0){ long[] c = gcd(f, g, mod); long[] w = div(f, c, mod); while(w.length != 1){ long[] y = gcd(w, c, mod); long[] z = div(w, y, mod); if(z.length > 1){ R.add(new FactorAndPower(z, i)); } i++; w = y; c = div(c, y, mod); } if(c.length != 1){ // c <- c^(1/p) long[] nc = new long[(c.length+mod-1)/mod]; for(int j = 0;j < c.length;j+=mod)nc[j/mod] = c[j]; c = nc; List res = doSquareFreeFactorization(c, mod); for(FactorAndPower fap : res){ fap.power *= mod; R.add(fap); } } }else{ long[] nf = new long[(f.length+mod-1)/mod]; for(int j = 0;j < f.length;j+=mod)nf[j/mod] = f[j]; f = nf; List res = doSquareFreeFactorization(f, mod); for(FactorAndPower fap : res){ fap.power *= mod; R.add(fap); } } return R; } // TODO check v^q-vへの改善がわからなかった public static List doCantorZassenhaus(FactorAndPower fap, int mod, Random gen) { assert mod % 2 == 1; Queue ret = new ArrayDeque<>(); int r = (fap.factor.length - 1) / fap.degree; int d = fap.degree; BigInteger E = BigInteger.valueOf(mod).pow(d).shiftRight(1); ret.add(fap); while(ret.size() < r){ long[] h = gen.longs(gen.nextInt(fap.factor.length-1)+1, 0, mod).toArray(); // choose randomly long[] g = sub(pow(h, E, fap.factor, mod), new long[]{1}, mod); for(int i = ret.size()-1;i >= 0;i--){ FactorAndPower u = ret.poll(); if(u.factor.length > d+1){ long[] gu = gcd(g, u.factor, mod); if(gu.length > 1 && gu.length < u.factor.length){ ret.add(new FactorAndPower(gu, u.power, u.degree)); ret.add(new FactorAndPower(div(u.factor, gu, mod), u.power, u.degree)); continue; } } ret.add(u); } } return new ArrayList<>(ret); } public static List doDistinctDegreeFactorization(long[] f, int mod) { long[] fstar = Arrays.copyOf(f, f.length); int i = 1; List ret = new ArrayList<>(); while(fstar.length >= 2*i){ long[] xq = modulo(mod, fstar, mod); long[][] Q = mulRowAndCompanionMatrixes(xq, f, mod); // Method 1 Q = pow(Q, i, mod); long[] R = sub(Q[0], new long[]{0, 1}, mod); long[] g = gcd(R, fstar, mod); if(g.length > 1){ ret.add(new FactorAndPower(g, 1, i)); fstar = div(fstar, g, mod); } i++; } if(fstar.length > 1){ ret.add(new FactorAndPower(fstar, 1, fstar.length-1)); } if(ret.isEmpty()){ ret.add(new FactorAndPower(f, 1, 1)); } return ret; } ///////////////// public static long[] mul(long[] a, long[] b, int mod) { if(a.length == 0)return new long[0]; long[] c = new long[a.length+b.length-1]; long big = (Long.MAX_VALUE / mod - mod) * mod; for(int i = 0;i < a.length;i++){ for(int j = 0;j < b.length;j++){ c[i+j] += a[i]*b[j]; if(c[i+j] >= big)c[i+j] -= big; } } for(int i = 0;i < c.length;i++)c[i] %= mod; return c; } public static long[] pow(long[] a, BigInteger E, long[] f, int mod) { long[] ret = {1}; for(int i = E.bitLength()-1;i >= 0;i--){ ret = modnaive(mul(ret, ret, mod), f, mod); if(E.testBit(i)){ ret = modnaive(mul(ret, a, mod), f, mod); } } return ret; } public static long[] sub(long[] a, long[] b, int mod) { long[] c = new long[Math.max(a.length, b.length)]; for(int i = 0;i < a.length;i++)c[i] += a[i]; for(int i = 0;i < b.length;i++)c[i] -= b[i]; for(int i = 0;i < c.length;i++)if(c[i] < 0)c[i] += mod; return normalize(c); } public static long[][] pow(long[][] A, long e, int mod) { long[][] MUL = A; int n = A.length; long[][] C = new long[n][n]; for(int i = 0;i < n;i++)C[i][i] = 1; for(;e > 0;e>>>=1) { if((e&1)==1)C = mul(C, MUL, mod); MUL = mul(MUL, MUL, mod); } return C; } public static long[][] mul(long[][] A, long[][] B, int mod) { assert A[0].length == B.length; int m = A.length; int n = A[0].length; int o = B[0].length; long[][] C = new long[m][o]; for(int i = 0;i < m;i++){ for(int j = 0;j < o;j++){ long sum = 0; for(int k = 0;k < n;k++){ sum += (long)A[i][k] * B[k][j]; sum %= mod; } C[i][j] = (int)sum; } } return C; } public static long[] modulo(long n, long[] f, int mod) { assert f.length > 0; int m = f.length; if(m == 1)return new long[0]; long ih = invl(f[m-1], mod); long[] a = new long[m-1]; for(int i = 0;i < m-1;i++)a[i] = ih*(mod-f[i])%mod; return poWCompanionMatrixesRow0(a, n, mod); } public static long[] d(long[] f, int mod) { if(f.length == 0)return new long[0]; long[] ret = new long[f.length-1]; for(int i = 1;i < f.length;i++){ ret[i-1] = f[i] * i % mod; } return normalize(ret); } public static long[] gcd(long[] a, long[] b, int mod) { while(b.length > 0){ long[] c = modnaive(a, b, mod); a = b; b = c; } if(a.length > 0){ long ih = invl(a[a.length-1], mod); for(int i = 0;i < a.length;i++){ a[i] = a[i] * ih % mod; } } return a; } static long[] normalize(long[] f) { for(int i = f.length-1;i >= 0;i--){ if(f[i] != 0){ return i == f.length-1 ? f : Arrays.copyOf(f, i+1); } } return new long[0]; } public static long[] modnaive(long[] a, long[] b, int mod) { int n = a.length, m = b.length; if(n-m+1 <= 0)return a; long[] r = Arrays.copyOf(a, n); long ib = invl(b[m-1], mod); for(int i = n-1;i >= m-1;i--){ long x = ib * r[i] % mod; for(int j = m-1;j >= 0;j--){ r[i+j-(m-1)] -= b[j]*x; r[i+j-(m-1)] %= mod; if(r[i+j-(m-1)] < 0)r[i+j-(m-1)] += mod; // r[i+j-(m-1)] = modh(r[i+j-(m-1)]+(long)mod*mod - b[j]*x, MM, HH, mod); } } return normalize(r); } public static long[] div(long[] a, long[] b, int mod) { int n = a.length, m = b.length; if(n-m+1 <= 0)return new long[0]; long[] r = Arrays.copyOf(a, n); long[] q = new long[n-m+1]; long ib = invl(b[m-1], mod); for(int i = n-1;i >= m-1;i--){ long x = ib * r[i] % mod; q[i-(m-1)] = x; for(int j = m-1;j >= 0;j--){ r[i+j-(m-1)] -= b[j]*x; r[i+j-(m-1)] %= mod; if(r[i+j-(m-1)] < 0)r[i+j-(m-1)] += mod; // r[i+j-(m-1)] = modh(r[i+j-(m-1)]+(long)mod*mod - b[j]*x, MM, HH, mod); } } return q; } public static long invl(long a, long mod) { long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p < 0 ? p + mod : p; } public static long[][] poWCompanionMatrixes(long[] A, long m, int mod) { int n = A.length; long[] u = new long[A.length]; u[0] = 1; long[][] CA = new long[n][n]; for(int i = 0;i < n-1;i++)CA[i][i+1] = 1; CA[n-1] = A; for(int i = 0;1L< A^(2n) CA = mulRowAndCompanionMatrixes(mulRowAndMatrix(CA[0], CA, mod), A, mod); } return mulRowAndCompanionMatrixes(u, A, mod); } public static long[] poWCompanionMatrixesRow0(long[] A, long m, int mod) { int n = A.length; long[] u = new long[A.length]; u[0] = 1; long[][] CA = new long[n][n]; for(int i = 0;i < n-1;i++)CA[i][i+1] = 1; CA[n-1] = A; for(int i = 0;1L< A^(2n) CA = mulRowAndCompanionMatrixes(mulRowAndMatrix(CA[0], CA, mod), A, mod); } return u; } public static long[][] mulRowAndCompanionMatrixes(long[] u, long[] A, int mod) { int n = u.length; long[][] NA = new long[n][]; NA[0] = Arrays.copyOf(u, n); for(int i = 1;i < n;i++){ long v = u[n-1]; for(int j = n-2;j >= 0;j--){ u[j+1] = u[j]; } u[0] = 0; for(int j = 0;j < n;j++){ u[j] += v * A[j]; u[j] %= mod; } NA[i] = Arrays.copyOf(u, n); } return NA; } private static long[] mulRowAndMatrix(long[] u, long[][] A, int mod) { int n = A.length; long[] nu = new long[n]; for(int j = 0;j < n;j++){ long s = 0; for(int i = 0;i < n;i++){ s += A[i][j] * u[i]; s %= mod; } nu[j] = s; } return nu; } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new N555().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }