ソースコード 拡げる

Copy
```long findBase(in ulong n, in ulong sumDigits)
{
import std.algorithm;
// 1-digit
if (n == sumDigits)
return n + 1;
foreach_reverse (digits; 2..n.binaryDigits)
{
immutable
bmin = n.minb(digits).max(1 + sumDigits / digits),
bmax = n.maxb(digits);
if (n <= sumDigits + bmin ^^ (digits - 1) - 1)
continue;
if (digits * (bmax - 1) < sumDigits)
continue;
if (2 < digits)
{
foreach (base; bmin..bmax+1)
if (base.f(n) == sumDigits)
return base;
continue;
}
// two-digit: larger base, larger sumdigit.
ulong left = bmin, right = bmax;
while (1 < right - left)
{
immutable mid = (left + right) >> 1;
if (mid.f(n) == sumDigits)
if ((mid - 1).f(n) == sumDigits)
return mid - 1;
else
return mid;
else if (mid.f(n) < sumDigits)
right = mid;
else
left = mid;
}
return (right.f(n) == sumDigits) ? right : -1;
}
return -1;
}

unittest
{
import std.experimental.logger;trace;
assert (87654.findBase(30) == 10);trace;
assert (87654.findBase(138) == 100);trace;
assert (87654.findBase(45678) == -1);trace;
assert (31415926535.findBase(1) == 31415926535);trace;
assert (1.findBase(31415926535) == -1);trace;
}

ulong f(in ulong base, in ulong n)
{
if (n < base)
return n;
return (n % base) + base.f(n / base);
}

ulong binaryDigits(in ulong n)
{
if (n < 3)
return n;
return (n >> 1).binaryDigits + 1;
}

unittest
{
assert (0.binaryDigits == 0);
assert (1.binaryDigits == 1);
assert (2.binaryDigits == 2);
assert (3.binaryDigits == 2);
assert (4.binaryDigits == 3);
assert (5.binaryDigits == 3);
assert (6.binaryDigits == 3);
assert (7.binaryDigits == 3);
assert (8.binaryDigits == 4);
}

ulong minb(in ulong n, in ulong digits)
{
return (n ^^ (real(1) / digits)).ffloor + 1;
}

ulong maxb(in ulong n, in ulong digits)
{
return (n ^^ (real(1) / (digits - 1))).ffloor;
}

auto ffloor(real x)
{
import std.math, std.conv;
return (x + 0x1p-16).floor.to!ulong;
}

void main()
{
import std.stdio, std.conv, std.string;
}
```

#### 提出情報

提出日時 2016-08-28 22:37:40+0900 D - 桁和 majiang D (DMD64 v2.070.1) 0 2565 Byte WA 15 ms 256 KB

#### ジャッジ結果

セット名 Sample All

 AC × 5
 AC × 29 WA × 18
セット名 テストケース
ケース名 結果 実行時間 メモリ
subtask1_100000000000_1.txt AC 4 ms 256 KB
subtask1_100000000000_100000000000.txt AC 4 ms 256 KB
subtask1_100000000000_2.txt WA 15 ms 256 KB
subtask1_100000000000_3.txt AC 15 ms 256 KB
subtask1_100000000000_50000000000.txt WA 4 ms 256 KB
subtask1_100000000000_50000000001.txt AC 3 ms 256 KB
subtask1_100000000000_99999999999.txt AC 4 ms 256 KB
subtask1_16983563041_1.txt AC 4 ms 256 KB
subtask1_1_1.txt AC 4 ms 256 KB
subtask1_1_2.txt AC 4 ms 256 KB
subtask1_1_31415926535.txt AC 4 ms 256 KB
subtask1_239484768_194586924.txt AC 4 ms 256 KB
subtask1_2_1.txt WA 4 ms 256 KB
subtask1_2_2.txt AC 3 ms 256 KB
subtask1_31415926535_1.txt AC 10 ms 256 KB
subtask1_49234683534_2461734011.txt AC 4 ms 256 KB
subtask1_4_1.txt WA 4 ms 256 KB
subtask1_58640129658_232122496.txt WA 4 ms 256 KB
subtask1_68719476735_35.txt AC 9 ms 256 KB
subtask1_68719476735_36.txt WA 13 ms 256 KB
subtask1_68719476735_37.txt WA 13 ms 256 KB
subtask1_68719476736_1.txt WA 4 ms 256 KB
subtask1_68719476736_2.txt AC 4 ms 256 KB
subtask1_72850192441_16865701.txt WA 3 ms 256 KB
subtask1_79285169301_27.txt AC 3 ms 256 KB
subtask1_82914867733_1676425945.txt WA 3 ms 256 KB
subtask1_8594813796_75700.txt AC 5 ms 256 KB
subtask1_87654_12345.txt WA 4 ms 256 KB
subtask1_87654_138.txt AC 4 ms 256 KB
subtask1_87654_30.txt AC 4 ms 256 KB
subtask1_87654_4294967308.txt AC 3 ms 256 KB
subtask1_87654_45678.txt AC 4 ms 256 KB
subtask1_97822032312_49157112.txt WA 4 ms 256 KB
subtask1_98750604051_977728851.txt WA 4 ms 256 KB
subtask1_99999515529_1.txt AC 15 ms 256 KB
subtask1_99999515529_316226.txt WA 11 ms 256 KB
subtask1_99999515529_316227.txt WA 11 ms 256 KB
subtask1_99999515529_316228.txt WA 11 ms 256 KB
subtask1_99999515529_49999757765.txt WA 4 ms 256 KB
subtask1_99999515529_49999757766.txt AC 3 ms 256 KB
subtask1_99999515530_2.txt AC 15 ms 256 KB
subtask1_99999999977_1.txt AC 15 ms 256 KB
subtask1_99999999977_2.txt AC 15 ms 256 KB
subtask1_99999999977_49999999989.txt WA 3 ms 256 KB
subtask1_99999999977_49999999990.txt AC 4 ms 256 KB
subtask1_99999999999_1.txt AC 15 ms 256 KB
subtask1_99999999999_100000000000.txt AC 3 ms 256 KB