Convert a number written in base a to base b and print it.
The number is at least 0, and its digits after the point may repeat forever.
The repeating part is written once, in parentheses: in base 10, 0.1666… is 0.1(6) and 0.142857142857… is 0.(142857).
Digit values of 10 or more use uppercase English letters: A = 10, B = 11, …, Z = 35.
The input number has one of three forms: I, I.F, I.F(R).
I is the integer part; it has at least one digit and does not start with 0 unless it is the single character 0.
F is the non-repeating part right after the point and may be empty; R is the repeating part and has at least one digit.
If there is a point, F and R are not both empty.
The fractional part of the input may not be written in its shortest form: notations such as 0.50, 0.1(0), 0.12(32) and 0.(9) also appear.
The output is the single notation of the same value in base b.
The integer part has no unnecessary leading zeros (an integer part of 0 is the single character 0).
If the value is an integer, no point is written.
If the digits after the point are finite, write them without parentheses; the last digit is not 0.
If they go on forever, make the repeating part start as early as possible, and among those choose the shortest one to put in parentheses.
A notation ending in endlessly repeated (b−1) is never used: in base 10, 0.(9) equals 1, so it is written as 1.
The first line gives a and b separated by a single space, and the second line gives the number in base a without spaces.
Input
2 ≤ a, b ≤ 36. The value of the integer part I is less than 10⁹ in decimal. If d is the number of digits written after the point (including those in parentheses), a^d ≤ 10,000. Every digit is 0–9 or A–Z with a value less than a.
Output
One line: the number in base b (uppercase, the single notation required by the rules above)
Example 1 · stdin
10 2
0.1
stdout
0.0(0011)
Example 2 · stdin
10 6
12.4(9)
stdout
20.3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Turn the number into a fraction, then do long division. For base-a I.F(R) where F has k digits and R has m digits, the value is p / q with q = a^k × (a^m − 1) and p = I × q + F × (a^m − 1) + R (without R, q = a^k and p = I × q + F). Write the quotient of p by q in base b; for the fraction, with remainder r, the quotient of r × b by q is the next digit and its remainder is the new r. When r becomes 0 the digits end; when an r seen before comes back, the digits repeat from the digit that r produced. Since r is less than q, one of the two happens within q steps. Dividing this way gives the earliest, shortest repeating part by itself, and never produces endlessly repeated (b−1). Python records when each r was seen in a dict, the others in an array of q slots (q ≤ 10,000; Craykon uses NewList(q, -1)). Reading digits differs by language: Python int(t, a), Java Long.parseLong(t, a) and JavaScript/TypeScript parseInt(t, a) read bases 2–36 directly, but an empty F throws in Python and Java and gives NaN in JavaScript, so the empty string is handled as 0 separately. C#'s Convert.ToInt64(t, base) accepts only bases 2, 8, 10 and 16, so it uses Digits.IndexOf(ch); C uses strchr(DIGITS, c) - DIGITS, C++ DIGITS.find(ch), and Craykon DIGITS.IndexOf(ch). Trap one: converting the integer part and the fractional part separately breaks when the fraction is exactly 1, as in 0.(9). Dividing 9 by 9 gives a first digit of 10, printing 0.A in base 10. Divide the whole p by q so the 1 carries into the integer part. Trap two: p grows to nearly 10⁹ × 10⁴ = 10¹³, which overflows int in Java, C#, C and C++ — use long/long long (Python integers have no limit, and JavaScript and Craykon are exact up to 2^53). Trap three: record the position of r before making a digit from it. Recording it after pushing the digit turns base-10 0.1(6) into 0.16(). Trap four: stop as soon as r becomes 0. Dividing 0 once more appends a 0, so decimal 0.5 becomes 0.10 in base 2. Trap five: when the integer part is 0, while (v > 0) never runs and 0.1 becomes .1 (the C, C++ and C# solutions use do-while). Trap six: JavaScript/TypeScript v.toString(b) and Java Long.toString(v, b) produce lowercase, so toUpperCase() is needed. Trap seven: in C, C++, Java and C#, computing a digit as c - '0' makes 'A' 17 instead of 10.
Pythonmain.py · 49 lines
DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"a, b = map(int, input().split())s = input().strip()# 정수 부분 / 끝나는 부분 F / 되풀이 부분 R 로 나눈다int_str, _, frac = s.partition(".")fixed, _, rep = frac.partition("(")rep = rep.rstrip(")")# 값을 분수 p / q 로 만든다: q = a^k × (a^m − 1) (R가 없으면 a^k)k, m = len(fixed), len(rep)f_val = int(fixed, a) if fixed else 0if m == 0: q = a ** k num = f_valelse: r_val = int(rep, a) q = a ** k * (a ** m - 1) num = f_val * (a ** m - 1) + r_valp = int(int_str, a) * q + num # 소수 부분이 1이 될 수도 있으니(0.(9)) 한꺼번에 나눈다whole, r = divmod(p, q)# 정수 부분을 b진법으로head = []while True: head.append(DIGITS[whole % b]) whole //= b if whole == 0: breakout = "".join(reversed(head))# 나머지를 b배 하며 긴 나눗셈. 같은 나머지가 다시 나오면 거기서부터 되풀이된다seen = {} # 나머지 → 그 나머지로 만든 자리의 위치digits = []while r != 0 and r not in seen: seen[r] = len(digits) r *= b digits.append(DIGITS[r // q]) r %= qif digits: if r == 0: out += "." + "".join(digits) else: start = seen[r] out += "." + "".join(digits[:start]) + "(" + "".join(digits[start:]) + ")"print(out)
JavaScriptmain.js · 43 lines
const DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";const [line1, line2] = require("fs").readFileSync(0, "utf8").trim().split(/\r?\n/);const [a, b] = line1.split(" ").map(Number);const s = line2.trim();// a진법 글자들을 값으로(빈 문자열이면 0). 값은 10^13쯤이라 2^53 안이다const read = (t) => (t === "" ? 0 : parseInt(t, a));// 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다const m = s.match(/^([0-9A-Z]+)(?:\.([0-9A-Z]*)(?:\(([0-9A-Z]+)\))?)?$/);const intStr = m[1], fixed = m[2] ?? "", rep = m[3] ?? "";// 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^klet q = a ** fixed.length;let num = read(fixed);if (rep !== "") { const am1 = a ** rep.length - 1; q *= am1; num = num * am1 + read(rep);}const p = read(intStr) * q + num; // 소수 부분이 1일 수도 있으니(0.(9)) 한꺼번에 나눈다let out = Math.floor(p / q).toString(b).toUpperCase(); // toString은 소문자를 낸다let r = p % q;// 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다const seen = new Array(q).fill(-1); // 나머지 → 그 나머지로 만든 자리의 위치const digits = [];while (r !== 0 && seen[r] === -1) { seen[r] = digits.length; r *= b; digits.push(DIGITS[Math.floor(r / q)]); r %= q;}if (digits.length > 0) { if (r === 0) out += "." + digits.join(""); else { const start = seen[r]; out += "." + digits.slice(0, start).join("") + "(" + digits.slice(start).join("") + ")"; }}console.log(out);
TypeScriptmain.ts · 46 lines
import { readFileSync } from "node:fs";const DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";const [line1, line2] = readFileSync(0, "utf8").trim().split(/\r?\n/);const [a, b]: number[] = line1.split(" ").map(Number);const s: string = line2.trim();// a진법 글자들을 값으로(빈 문자열이면 0). 값은 10^13쯤이라 2^53 안이다const read = (t: string): number => (t === "" ? 0 : parseInt(t, a));// 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다const m = s.match(/^([0-9A-Z]+)(?:\.([0-9A-Z]*)(?:\(([0-9A-Z]+)\))?)?$/)!;const intStr: string = m[1];const fixed: string = m[2] ?? "";const rep: string = m[3] ?? "";// 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^klet q: number = a ** fixed.length;let num: number = read(fixed);if (rep !== "") { const am1 = a ** rep.length - 1; q *= am1; num = num * am1 + read(rep);}const p: number = read(intStr) * q + num; // 소수 부분이 1일 수도 있으니(0.(9)) 한꺼번에 나눈다let out: string = Math.floor(p / q).toString(b).toUpperCase(); // toString은 소문자를 낸다let r: number = p % q;// 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다const seen: number[] = new Array<number>(q).fill(-1); // 나머지 → 그 나머지로 만든 자리의 위치const digits: string[] = [];while (r !== 0 && seen[r] === -1) { seen[r] = digits.length; r *= b; digits.push(DIGITS[Math.floor(r / q)]); r %= q;}if (digits.length > 0) { if (r === 0) out += "." + digits.join(""); else { const start = seen[r]; out += "." + digits.slice(0, start).join("") + "(" + digits.slice(start).join("") + ")"; }}console.log(out);
JavaMain.java · 71 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;public class Main { static final String DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // a진법 글자들을 값으로(빈 문자열이면 0) static long read(String t, int a) { return t.isEmpty() ? 0 : Long.parseLong(t, a); } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] ab = in.readLine().trim().split(" "); int a = Integer.parseInt(ab[0]), b = Integer.parseInt(ab[1]); String s = in.readLine().trim(); // 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다 String intStr = s, fixed = "", rep = ""; int dot = s.indexOf('.'); if (dot >= 0) { intStr = s.substring(0, dot); String frac = s.substring(dot + 1); int open = frac.indexOf('('); if (open >= 0) { fixed = frac.substring(0, open); rep = frac.substring(open + 1, frac.length() - 1); } else { fixed = frac; } } // 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^k long q = 1; for (int i = 0; i < fixed.length(); i++) q *= a; long num = read(fixed, a); if (!rep.isEmpty()) { long am1 = 1; for (int i = 0; i < rep.length(); i++) am1 *= a; am1 -= 1; q *= am1; num = num * am1 + read(rep, a); } long p = read(intStr, a) * q + num; // 10^13까지 커지니 long. 소수 부분이 1일 수도 있어 한꺼번에 나눈다 StringBuilder out = new StringBuilder(Long.toString(p / q, b).toUpperCase()); // toString은 소문자를 낸다 int r = (int) (p % q); // q < 10000이라 나머지는 int에 들어간다 // 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다 int[] seen = new int[(int) q]; // 나머지 → 그 나머지로 만든 자리의 위치 Arrays.fill(seen, -1); StringBuilder digits = new StringBuilder(); while (r != 0 && seen[r] == -1) { seen[r] = digits.length(); r *= b; digits.append(DIGITS.charAt((int) (r / q))); r %= q; } if (digits.length() > 0) { out.append('.'); if (r == 0) out.append(digits); else { int start = seen[r]; out.append(digits, 0, start).append('(').append(digits, start, digits.length()).append(')'); } } System.out.println(out); }}
C#Main.cs · 86 lines
using System;using System.Text;class Program{ const string Digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // a진법 글자들을 값으로(빈 문자열이면 0). Convert.ToInt64(s, base)는 2·8·10·16진법만 받는다 static long Read(string t, int a) { long v = 0; foreach (char ch in t) v = v * a + Digits.IndexOf(ch); return v; } static void Main() { string[] ab = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(ab[0]), b = int.Parse(ab[1]); string s = Console.ReadLine().Trim(); // 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다 string intStr = s, fixedPart = "", rep = ""; int dot = s.IndexOf('.'); if (dot >= 0) { intStr = s[..dot]; string frac = s[(dot + 1)..]; int open = frac.IndexOf('('); if (open >= 0) { fixedPart = frac[..open]; rep = frac[(open + 1)..^1]; } else fixedPart = frac; } // 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^k long q = 1; for (int i = 0; i < fixedPart.Length; i++) q *= a; long num = Read(fixedPart, a); if (rep.Length > 0) { long am1 = 1; for (int i = 0; i < rep.Length; i++) am1 *= a; am1 -= 1; q *= am1; num = num * am1 + Read(rep, a); } long p = Read(intStr, a) * q + num; // 10^13까지 커지니 long. 소수 부분이 1일 수도 있어 한꺼번에 나눈다 long whole = p / q; var head = new StringBuilder(); do { head.Insert(0, Digits[(int)(whole % b)]); // 낮은 자리부터 나오니 앞에 끼운다 whole /= b; } while (whole > 0); long r = p % q; // 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다 int[] seen = new int[q]; // 나머지 → 그 나머지로 만든 자리의 위치 Array.Fill(seen, -1); var digits = new StringBuilder(); while (r != 0 && seen[r] == -1) { seen[r] = digits.Length; r *= b; digits.Append(Digits[(int)(r / q)]); r %= q; } var outSb = new StringBuilder(head.ToString()); if (digits.Length > 0) { string d = digits.ToString(); if (r == 0) outSb.Append('.').Append(d); else { int start = seen[r]; outSb.Append('.').Append(d[..start]).Append('(').Append(d[start..]).Append(')'); } } Console.WriteLine(outSb); }}
C++main.cpp · 79 lines
#include <iostream>#include <string>#include <vector>#include <algorithm>const std::string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";// a진법 글자들을 값으로(빈 문자열이면 0)long long readPart(const std::string &t, int a) { long long v = 0; for (char ch : t) v = v * a + (long long)DIGITS.find(ch); return v;}long long power(int a, std::size_t k) { long long v = 1; for (std::size_t i = 0; i < k; i++) v *= a; return v;}int main() { int a, b; std::string s; std::cin >> a >> b >> s; // 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다 std::string intStr = s, fixed, rep; auto dot = s.find('.'); if (dot != std::string::npos) { intStr = s.substr(0, dot); std::string frac = s.substr(dot + 1); auto open = frac.find('('); if (open != std::string::npos) { fixed = frac.substr(0, open); rep = frac.substr(open + 1, frac.size() - open - 2); } else { fixed = frac; } } // 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^k long long q = power(a, fixed.size()); long long num = readPart(fixed, a); if (!rep.empty()) { long long am1 = power(a, rep.size()) - 1; q *= am1; num = num * am1 + readPart(rep, a); } long long p = readPart(intStr, a) * q + num; // 10^13까지 커지니 long long long long whole = p / q; // 소수 부분이 1일 수도 있으니(0.(9)) 한꺼번에 나눈다 std::string out; do { out += DIGITS[whole % b]; whole /= b; } while (whole > 0); std::reverse(out.begin(), out.end()); // 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다 std::vector<int> seen(q, -1); // 나머지 → 그 나머지로 만든 자리의 위치 std::string digits; long long r = p % q; while (r != 0 && seen[r] == -1) { seen[r] = (int)digits.size(); r *= b; digits += DIGITS[r / q]; r %= q; } if (!digits.empty()) { out += '.'; if (r == 0) out += digits; else { int start = seen[r]; out += digits.substr(0, start) + "(" + digits.substr(start) + ")"; } } std::cout << out << '\n';}
Cmain.c · 76 lines
#include <stdio.h>#include <string.h>static const char *DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";/* s[from..to) 의 a진법 글자들을 값으로(비어 있으면 0) */static long long read_part(const char *s, int from, int to, int a) { long long v = 0; for (int i = from; i < to; i++) v = v * a + (long long)(strchr(DIGITS, s[i]) - DIGITS); /* 'A'는 10: c - '0'이 아니다 */ return v;}static long long power(int a, int k) { long long v = 1; while (k-- > 0) v *= a; return v;}int main(void) { int a, b; char s[128]; if (scanf("%d %d %127s", &a, &b, s) != 3) return 0; int len = (int)strlen(s); /* 정수 부분 [0, dot) / 끝나는 부분 [dot+1, open) / 되풀이 부분 [open+1, len-1) */ char *pdot = strchr(s, '.'); int dot = pdot ? (int)(pdot - s) : len; char *popen = strchr(s, '('); int open = popen ? (int)(popen - s) : len; int fixed_from = dot < len ? dot + 1 : len; /* 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^k */ long long q = power(a, open - fixed_from); long long num = read_part(s, fixed_from, open, a); if (open < len) { long long am1 = power(a, len - 1 - (open + 1)) - 1; q *= am1; num = num * am1 + read_part(s, open + 1, len - 1, a); } long long p = read_part(s, 0, dot, a) * q + num; /* 10^13까지 커지니 long long */ long long whole = p / q; /* 소수 부분이 1일 수도 있으니(0.(9)) 한꺼번에 나눈다 */ char head[64]; int hl = 0; do { head[hl++] = DIGITS[whole % b]; whole /= b; } while (whole > 0); for (int i = hl - 1; i >= 0; i--) putchar(head[i]); /* 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다 */ static int seen[10000]; /* 나머지 → 그 나머지로 만든 자리의 위치 */ static char digits[10001]; for (int i = 0; i < q; i++) seen[i] = -1; int n = 0; long long r = p % q; while (r != 0 && seen[r] == -1) { seen[r] = n; r *= b; digits[n++] = DIGITS[r / q]; r %= q; } digits[n] = '\0'; if (n > 0) { putchar('.'); if (r == 0) fputs(digits, stdout); else { int start = seen[r]; printf("%.*s(%s)", start, digits, digits + start); } } putchar('\n'); return 0;}
Craykonmain.cray · 99 lines
DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";// a진법 글자들을 앞에서부터 읽어 값으로 만든다(빈 문자열이면 0)읽기(s, a){ v = 0; foreach (ch in s) { v = v * a + DIGITS.IndexOf(ch); } return v;}거듭(a, k){ v = 1; for (i = 0; i < k; i += 1) { v = v * a; } return v;}ab = Console.ReadNumbers();a = ab[0];b = ab[1];s = Console.ReadLine().Trim();// 정수 부분 / 끝나는 부분 / 되풀이 부분으로 나눈다intStr = s;fixed = "";rep = "";dot = s.IndexOf(".");if (dot >= 0){ intStr = s.Substring(0, dot); frac = s.Substring(dot + 1); open = frac.IndexOf("("); if (open >= 0) { fixed = frac.Substring(0, open); rep = frac.Substring(open + 1, frac.Length - open - 2); } else { fixed = frac; }}// 값을 분수 p / q 로: q = a^k × (a^m − 1), 되풀이 부분이 없으면 a^kq = 거듭(a, fixed.Length);num = 읽기(fixed, a);if (rep.Length > 0){ am1 = 거듭(a, rep.Length) - 1; q = q * am1; num = num * am1 + 읽기(rep, a);}p = 읽기(intStr, a) * q + num; // 소수 부분이 1일 수도 있으니(0.(9)) 한꺼번에 나눈다whole = Mathf.Quot(p, q);r = p % q;// 정수 부분을 b진법으로out = "";while (true){ out = DIGITS[whole % b] + out; whole = Mathf.Quot(whole, b); if (whole == 0) { break; }}// 긴 나눗셈: 같은 나머지가 다시 나오면 거기서부터 되풀이된다seen = NewList(q, -1); // 나머지 → 그 나머지로 만든 자리의 위치digits = [];while (r != 0 && seen[r] == -1){ seen[r] = digits.Count; r = r * b; digits.Add(DIGITS[Mathf.Quot(r, q)]); r = r % q;}if (digits.Count > 0){ if (r == 0) { out = out + "." + digits.Join(""); } else { start = seen[r]; out = out + "." + digits.GetRange(0, start).Join("") + "(" + digits.GetRange(start, digits.Count - start).Join("") + ")"; }}Console.WriteLine(out);