結果

問題 No.757 チャンパーノウン定数 (2)
ユーザー te-sh
提出日時 2018-12-07 15:43:36
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 4,343 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 111,744 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-06-13 02:02:53
合計ジャッジ時間 2,494 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;
auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}
void main()
{
int b; readV(b);
string s; readV(s);
if (s == "1") {
writeln(1);
return;
}
auto d = GmpInt(s, b)-1;
auto len(int x)
{
auto bp = GmpInt(b)^^x;
return bp*x - (bp-1)/(b-1);
}
auto es = iota(0, s.length.to!int+1).map!(x => tuple(x, len(x))).assumeSorted!"a[1]<b[1]";
auto e = es.lowerBound(tuple(1, d)).back;
auto f = e[0]+1;
d -= e[1];
auto g = d/f + GmpInt(b)^^(f-1), h = d%GmpInt(f);
writeln(g.toString(b)[h.toLong]);
}
struct GmpInt
{
__mpz_struct z;
this(long v)
{
__gmpz_init(&z);
__gmpz_set_si(&z, v);
}
this(string s, int base = 10)
{
import std.string;
__gmpz_init(&z);
__gmpz_set_str(&z, s.toStringz, base);
}
auto toLong()
{
return __gmpz_get_si(&z);
}
auto toString(int base = 10)
{
import std.string;
auto sz = __gmpz_sizeinbase(&z, base);
auto buf = new char[](sz + 2);
__gmpz_get_str(buf.ptr, base, &z);
return buf.ptr.fromStringz;
}
auto opCmp(GmpInt v)
{
return __gmpz_cmp(&z, &v.z);
}
auto opBinary(string op)(GmpInt v)
if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%")
{
auto r = GmpInt(0);
static if (op == "+") __gmpz_add(&r.z, &z, &v.z);
else if (op == "-") __gmpz_sub(&r.z, &z, &v.z);
else if (op == "*") __gmpz_mul(&r.z, &z, &v.z);
else if (op == "/") __gmpz_tdiv_q(&r.z, &z, &v.z);
else if (op == "%") __gmpz_mod(&r.z, &z, &v.z);
return r;
}
auto opBinary(string op)(ulong v)
if (op == "+" || op == "-" || op == "*" || op == "/" || op == "^^")
{
auto r = GmpInt(0);
static if (op == "+") __gmpz_add_ui(&r.z, &z, v);
else if (op == "-") __gmpz_sub_ui(&r.z, &z, v);
else if (op == "*") __gmpz_mul_ui(&r.z, &z, v);
else if (op == "/") __gmpz_tdiv_q_ui(&r.z, &z, v);
else if (op == "^^") __gmpz_pow_ui(&r.z, &z, v);
return r;
}
auto opOpAssign(string op)(GmpInt v)
if (op == "+" || op == "-" || op == "*" || op == "/" || op == "%")
{
static if (op == "+") __gmpz_add(&z, &z, &v.z);
else if (op == "-") __gmpz_sub(&z, &z, &v.z);
else if (op == "*") __gmpz_mul(&z, &z, &v.z);
else if (op == "/") __gmpz_tdiv_q(&z, &z, &v.z);
else if (op == "%") __gmpz_mod(&z, &z, &v.z);
return this;
}
auto opOpAssign(string op)(ulong v)
if (op == "+" || op == "-" || op == "*" || op == "/" || op == "^^")
{
static if (op == "+") __gmpz_add_ui(&z, &z, v);
else if (op == "-") __gmpz_sub_ui(&z, &z, v);
else if (op == "*") __gmpz_mul_ui(&z, &z, v);
else if (op == "/") __gmpz_tdiv_q_ui(&z, &z, v);
return this;
}
GmpInt sqrt()
{
auto r = GmpInt(0);
__gmpz_sqrt(&r.z, &z);
return r;
}
size_t popcnt()
{
return __gmpz_popcount(&z);
}
int probabPrime(int reps)
{
return __gmpz_probab_prime_p(&z, reps);
}
}
extern(C) pragma(inline, false)
{
alias __mp_limb_t = ulong;
struct __mpz_struct
{
int _mp_alloc;
int _mp_size;
__mp_limb_t* _mp_d;
}
alias mpz_srcptr = const(__mpz_struct)*;
alias mpz_ptr = __mpz_struct*;
void __gmpz_init(mpz_ptr);
void __gmpz_set_si(mpz_ptr, long);
int __gmpz_set_str(mpz_ptr, const char*, int);
long __gmpz_get_si(mpz_srcptr);
char *__gmpz_get_str(char*, int, mpz_srcptr);
size_t __gmpz_sizeinbase(mpz_srcptr, int);
int __gmpz_cmp(mpz_srcptr, mpz_srcptr);
void __gmpz_add(mpz_ptr, mpz_srcptr, mpz_srcptr);
void __gmpz_add_ui(mpz_ptr, mpz_srcptr, ulong);
void __gmpz_sub(mpz_ptr, mpz_srcptr, mpz_srcptr);
void __gmpz_sub_ui(mpz_ptr, mpz_srcptr, ulong);
void __gmpz_mul(mpz_ptr, mpz_srcptr, mpz_srcptr);
void __gmpz_mul_ui(mpz_ptr, mpz_srcptr, ulong);
void __gmpz_tdiv_q(mpz_ptr, mpz_srcptr, mpz_srcptr);
ulong __gmpz_tdiv_q_ui(mpz_ptr, mpz_srcptr, ulong);
void __gmpz_mod(mpz_ptr, mpz_srcptr, mpz_srcptr);
void __gmpz_pow_ui(mpz_ptr, mpz_srcptr, ulong);
void __gmpz_sqrt(mpz_ptr, mpz_srcptr);
size_t __gmpz_popcount(mpz_srcptr);
int __gmpz_probab_prime_p(mpz_ptr, int reps);
}
pragma(lib, "gmp");
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0