import std.stdio, std.conv, std.string, std.bigint; import std.math, std.random, std.datetime; import std.array, std.range, std.algorithm, std.container; string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; } void main(){ int b = read.to!int; string d = readln.chomp; debug writeln("b: ", b); debug writeln("d: ", d); // 第k群(k桁の数たちの中にいる) int k = 1 + uplimit(1, 100, (int x) => wk(b, x).lt(d)); debug writeln("k: ", k); // 第k群の第j文字目 string j = d.sub(wk(b, k - 1), b); debug writeln("j: ", j); // 第k群の何個目の数を構成している文字か string m = j.add((k - 1).to!string, b).div(k, b); debug writeln("m: ", m); // それは何という数か string x = ("1" ~ ("0".repeat(k - 1))).sub("1", b).add(m, b); debug writeln("x: ", x); // その何桁目か int y = j.mod(k, b); if(y == 0) y += k; debug writeln("y: ", y); // ずばり答えは x[y - 1].writeln; /* debug foreach(x; [ ["5", "8"], ["8", "5"], ["5", "5"], ["50", "8"], ["80", "8"], ["80", "5"], ["5", "80"], ["5", "50"], ["8", "50"], ["54", "54"], ["52", "53"], ["85", "82"], ]) writeln(x[0], " <= ", x[1], " : ", le(x[0], x[1])); */ /* debug foreach(x; [ ["423", "144", "9"], ["836", "542", "9"], ["836", "543", "9"], ["4", "108", "10"], ["189", "9", "10"] ]) writeln(x[0], " + ", x[1], " (", x[2], ")= ", x[0].add(x[1], x[2].to!int)); debug foreach(x; [ ["846", "512", "9"], ["836", "542", "9"], ["106", "42", "9"], ["106", "2", "9"], ["106", "8", "9"], ["140", "140", "6"] ]) writeln(x[0], " - ", x[1], " (", x[2], ")= ", x[0].sub(x[1], x[2].to!int)); */ /* debug foreach(x; [ [10, 1], [10, 2], [10, 3], [10, 4], [10, 5], [10, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], ]) writeln(x[0], ", ", x[1], " => ", wk(x[0], x[1])); */ /* debug foreach(x; [ [0, 10, 6], [0, 10, 0], [0, 10, 10], [0, 10, 100], ]) writeln(x[0], ", ", x[1], ", ( x < ", x[2], " ) => ", uplimit(x[0], x[1], (int k) => k < x[2])); */ /* debug foreach(x; [ [100, 5, 10], [100, 5, 9], [83, 5, 10], [83, 5, 9], [3, 8, 9], [1000, 3, 9], [305, 5, 10], [900, 9, 10] ]) writeln(x[0], " / ", x[1], " (" , x[2], ")= ", x[0].to!string.div(x[1], x[2]), " ... ", x[0].to!string.mod(x[1], x[2])); */ } // 整数としての比較 bool lt(string a, string b){ if(a.length < b.length) return 1; if(a.length > b.length) return 0; if(a < b) return 1; if(a > b) return 0; return 0; } bool le(string a, string b){ if(a.length < b.length) return 1; if(a.length > b.length) return 0; if(a < b) return 1; if(a > b) return 0; return 1; } // 整数としての足し算 string add(string u, string v, int b){ string ux, vx, ansx; foreach_reverse(c; u) ux ~= c; foreach_reverse(c; v) vx ~= c; while(ux.length < vx.length) ux ~= '0'; while(vx.length < ux.length) vx ~= '0'; int f = 0; for(int i = 0; i < ux.length; i ++){ int iu = ("" ~ ux[i]).to!int, iv = ("" ~ vx[i]).to!int; if(iu + iv + f < b) ansx ~= (iu + iv + f).to!string, f = 0; else ansx ~= (iu + iv + f - b).to!string, f = 1; } if(f) ansx ~= "1"; string ans; foreach_reverse(c; ansx){ if(ans.length == 0 && c == '0') continue; ans ~= c; } if(ans == "") ans = "0"; return ans; } // 整数としての引き算 string sub(string u, string v, int b){ string ux, vx, ansx; foreach_reverse(c; u) ux ~= c; foreach_reverse(c; v) vx ~= c; while(ux.length < vx.length) ux ~= '0'; while(vx.length < ux.length) vx ~= '0'; int f = 0; for(int i = 0; i < ux.length; i ++){ int iu = ("" ~ ux[i]).to!int, iv = ("" ~ vx[i]).to!int; if(iu >= iv + f) ansx ~= (iu - iv - f).to!string, f = 0; else ansx ~= (iu + b - iv - f).to!string, f = 1; } string ans; foreach_reverse(c; ansx){ if(ans.length == 0 && c == '0') continue; ans ~= c; } if(ans == "") ans = "0"; return ans; } // 割り算 string div(string u, int k, int b){ int tmp; string ans; foreach(c; u){ tmp *= b; tmp += ("" ~ c).to!int; if(tmp >= k) ans ~= (tmp / k).to!string, tmp %= k; else if(ans.length > 0) ans ~= '0'; } if(ans == "") ans = "0"; return ans; } int mod(string u, int k, int b){ int tmp; string ans; foreach(c; u){ tmp *= b; tmp += ("" ~ c).to!int; if(tmp >= k) ans ~= (tmp / k).to!string, tmp %= k; else ans ~= '0'; } return tmp; } // 第k群の終わりまでで何文字あるかを表すb進数の文字列 string wk(int b, int k){ if(k == 0) return "0"; string res; if(k > 1) res ~= repres(k - 1, b); foreach(i; 0 .. k - 1) res ~= (b - 2).to!string; res ~= (b - 1).to!string; return res; } // b進法でのx string repres(int x, int b){ string tmp; while(x > 0){ tmp ~= (x % b).to!string; x /= b; } string res; foreach_reverse(c; tmp) res ~= c; if(res == "") res = "0"; return res; } // b進法でのxの桁数 int length(int b, int x){ long tmp = 1; int res = 0; while(tmp < x) tmp *= b, res += 1; return res; } // fをみたす最大 int uplimit(int a, int c, bool delegate(int) f){ if(f(c)) return c; if(! f(a)) return a - 1; while(a + 1 < c){ int b = (a + c) / 2; if(f(b)) a = b; else c = b; } return a; } // 繰り返し string repeat(string s, int t){ string res; foreach(i; 0 .. t) res ~= s; return res; }