#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__) #define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } mt19937 mt(8901016); inline int rand_int(int l, int h) { return uniform_int_distribution<>(l, h)(mt); } #ifdef __MAI #define getchar_unlocked getchar #define putchar_unlocked putchar #endif #ifdef __VSCC #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #endif #ifdef __MAI #define getchar_unlocked getchar #define putchar_unlocked putchar #endif #ifdef __VSCC #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #endif namespace { #define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiblechar(cc); cc = getchar_unlocked()); for (; isvisiblechar(cc); cc = getchar_unlocked()) var.push_back(cc); } template void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; } }; } MaiScanner scanner; template //typedef int T; class segtree { int size; vector valdata; vector addtree; vector mintree; vector maxtree; int _geti(const vector& v, int idx) const { if (size - 1 <= idx) return (idx - size + 1); // if (idx < 0) return idx; return v[idx]; } public: segtree(int n) { size = 8; while (size < n) size <<= 1; mintree.resize(size); maxtree.resize(size); valdata.resize(size); addtree.resize(size); } // tree初期化 void flat() { for (int i = size - 2; 0 <= i; --i) { int c = 2 * i + 1; if (size - 1 <= c) { mintree[i] = c - size + 1; maxtree[i] = c - size + 1; } else { mintree[i] = mintree[c]; maxtree[i] = maxtree[c]; } } } // TODO:verify // addtreeを0にして,valdataに加算する. void apply(T sum = 0, int ptr = 0) { if (size - 1 <= ptr) { valdata[ptr - size + 1] += sum; } else { sum += addtree[ptr]; apply(sum, ptr * 2 + 1); apply(sum, ptr * 2 + 2); addtree[ptr] = 0; } } void fill(T val) { std::fill(valdata.begin(), valdata.end(), val); std::fill(addtree.begin(), addtree.end(), 0); flat(); } // T operator[](int index) const { // // } T getval(int index) const { T sum = valdata[index]; index += size - 1; while (0 < index) { index = (index - 1) / 2; // 親へ移動 sum += addtree[index]; } return sum; } void setval(int index, const T e) { valdata[index] = e; for (int i = index + size - 1; 0 < i;) { i = (i - 1) / 2; // 親へ移動 valdata[index] -= addtree[i]; } index += size - 1; while (0 < index) { index = (index - 1) / 2; // 親へ移動 int c1 = index * 2 + 1; int c2 = index * 2 + 2; int i1, i2; i1 = _geti(mintree, c1); i2 = _geti(mintree, c2); mintree[index] = getval(i1) < getval(i2) ? i1 : i2; i1 = _geti(maxtree, c1); i2 = _geti(maxtree, c2); maxtree[index] = getval(i1) > getval(i2) ? i1 : i2; } } void addvalrange(int begin, int end, const T e, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return; if (begin <= rangebegin && rangeend <= end) { if (size - 1 <= ptr) valdata[ptr - size + 1] += e; else addtree[ptr] += e; return; } int rangemid = (rangebegin + rangeend) / 2; addvalrange(begin, end, e, ptr * 2 + 1, rangebegin, rangemid); addvalrange(begin, end, e, ptr * 2 + 2, rangemid, rangeend); int i1, i2; i1 = _geti(mintree, ptr * 2 + 1); i2 = _geti(mintree, ptr * 2 + 2); mintree[ptr] = getval(i1) < getval(i2) ? i1 : i2; i1 = _geti(maxtree, ptr * 2 + 1); i2 = _geti(maxtree, ptr * 2 + 2); maxtree[ptr] = getval(i1) > getval(i2) ? i1 : i2; } int getminrangeIdx(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) const { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return begin; // note:範囲外なら適当な範囲内のindexを返す if (begin <= rangebegin && rangeend <= end) return _geti(mintree, ptr); int rangemid = (rangebegin + rangeend) / 2; int l = getminrangeIdx(begin, end, ptr * 2 + 1, rangebegin, rangemid); int r = getminrangeIdx(begin, end, ptr * 2 + 2, rangemid, rangeend); if (getval(l) <= getval(r)) return l; else return r; } T getminrange(int begin, int end) { return getval(getminrangeIdx(begin, end)); } int getmaxrangeIdx(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) const { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return begin; // note:範囲外なら適当な範囲内のindexを返す if (begin <= rangebegin && rangeend <= end) return _geti(maxtree, ptr); int rangemid = (rangebegin + rangeend) / 2; int l = getmaxrangeIdx(begin, end, ptr * 2 + 1, rangebegin, rangemid); int r = getmaxrangeIdx(begin, end, ptr * 2 + 2, rangemid, rangeend); if (getval(l) >= getval(r)) return l; else return r; } T getmaxrange(int begin, int end) { return getval(getmaxrangeIdx(begin, end)); } }; int m, n, kei; ll cc, vv; //ll dp[200010]; int main() { scanner >> n >> cc >> vv; //fill(dp, dp + 200010, (ll)5e15); segtree dp(2 * n + 10); dp.fill(5e15); dp.setval(0, 0); dp.setval(1, 0); iterate(i, 1, n) { ll t = 1; ll nice = dp.getminrange(i, 2*n + 5); for (int j = i * 2; j <= n; j += i) { ll now = dp.getval(j); ll to = nice + cc + vv*t; if (to < now) { dp.setval(j, to); } ++t; } //debuga(dp,n+1) } ll best = 5e15; best = dp.getminrange(n, 2 * n + 5); cout << best << endl; return 0; }