b 进制算盘在每一位上放 0 到 b - 1 颗珠子来表示一个数。 把一个数放到 b 进制算盘上需要的珠子数，等于把这个数写成 b 进制时各位数字之和。 例如 10 写成 2 进制是 1010，需要 2 颗珠子；写成 10 进制是 10，需要 1 颗珠子。 给出 q 个询问。 每个询问给出一个数 n 和 k 个算盘的进制。 对每个询问，输出表示 n 时用珠子最少的算盘的进制，以及那个珠子数。 如果珠子最少的算盘有多个，选其中在输入里最先写出的那个。 请试着写一个函数，接收数和进制，返回珠子数，并对每个算盘调用它来解题。 不过评测只看输出，所以无法检查你是否写了函数。
输入
第一行给出 q。 接下来 q 行，每行一个询问：n、k，然后是 k 个进制，用一个空格隔开。 1 ≤ q ≤ 1,000，1 ≤ n ≤ 1,000,000,000,000,000（10 的 15 次方），1 ≤ k ≤ 8，进制是 2 到 1,000 之间的整数，同一个进制可能出现多次
输出
每个询问输出一行：选中的算盘的进制和它的珠子数，用一个空格隔开
样例 1 · stdin
3
10 3 2 3 10
5 2 4 2
10000000000 2 7 10
stdout
10 1
4 2
10 1
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
定义函数的样子因语言而异。 Python 写 def beads(n, b):，JS 写 function beads(n, b) { }，TS 还要写上 n: number 和返回类型。 Java 和 C# 在类里把类型全部写出，如 static int beads(long n, int b)，C 和 C++ 也要写类型。 Craykon 只写名字和参数：beads(n, b) { … 返回 total; }。 定义和调用的先后也不同。 C 里调用处的上方必须有函数或函数原型（int beads(long long n, int b);）。 没有的话，gcc 14 和 clang 会报编译错误，gcc 11 只给出警告就继续。 Python 在 def 执行之前调用，会以 NameError 停下。 JS 的 function 声明和 Craykon 的函数即使写在下面，也能在上面调用；但 JS 里用 const beads = (n, b) => … 定义的函数，在那一行之前调用会 ReferenceError。 把数作为参数传进去时，八种语言都是复制值，所以在函数里把 n 一直除到 0，调用方的 n 也不变。 陷阱一：在 C++ 里把参数写成 long long& n，它就不是副本，而是调用方的 n 本身。 第一次调用把 n 变成 0，示例的第一行不是 10 1 而是 3 0。 陷阱二：n 放不进 32 位整数。 在 C 里把参数写成 int n，传值时会被悄悄截断，示例的第三行变成 10 29。 Java 和 C# 把 long 传给 int 参数时会报编译错误。 陷阱三：把存放总和的变量放在函数外面，调用结束后值还留着。 下一次调用会接着前面的总和继续加，示例的第一行变成 2 2。 要在函数里新建一个从 0 开始的变量。 陷阱四：珠子数相同时用 <= 比较，会换成后写出的算盘。 示例的第二行不是 4 2 而是 2 2。 JS、TS 没有整数除法运算符，所以题解先减去余数再除（(n - n % b) / b）。 Python 用 //，Craykon 用 数学.商。
Pythonmain.py · 26 行
import sysdef beads(n, b): """n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)""" total = 0 while n > 0: total += n % b n //= b # 매개변수 n만 줄어든다. 부른 쪽의 수는 그대로다 return totallines = sys.stdin.read().split("\n")q = int(lines[0])out = []for line in lines[1:q + 1]: nums = list(map(int, line.split())) n, bases = nums[0], nums[2:] best_base = bases[0] best = beads(n, best_base) for b in bases[1:]: count = beads(n, b) if count < best: # 같으면 먼저 적힌 주판을 그대로 둔다 best, best_base = count, b out.append(f"{best_base} {best}")print("\n".join(out))
JavaScriptmain.js · 30 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const out = [];for (let i = 1; i <= q; i++) { const nums = lines[i].trim().split(" ").map(Number); const n = nums[0]; let bestBase = nums[2]; let best = beads(n, bestBase); // function 선언은 끌어올려져서 정의보다 먼저 부를 수 있다 for (let j = 3; j < nums.length; j++) { const count = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n, b) { let total = 0; while (n > 0) { const digit = n % b; total += digit; n = (n - digit) / b; // JS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}
TypeScriptmain.ts · 32 行
import { readFileSync } from "node:fs";// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n: number, b: number): number { let total = 0; while (n > 0) { const digit: number = n % b; total += digit; n = (n - digit) / b; // TS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= q; i++) { const nums: number[] = lines[i].trim().split(" ").map(Number); const n: number = nums[0]; let bestBase: number = nums[2]; let best: number = beads(n, bestBase); for (let j = 3; j < nums.length; j++) { const count: number = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));
JavaMain.java · 39 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int beads(long n, int b) { int total = 0; while (n > 0) { total += (int) (n % b); n /= b; } return total; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); long n = Long.parseLong(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int bestBase = Integer.parseInt(st.nextToken()); int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b = Integer.parseInt(st.nextToken()); int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } out.append(bestBase).append(' ').append(best).append('\n'); } System.out.print(out); }}
C#Main.cs · 42 行
using System;using System.Text;class Program{ // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int Beads(long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total; } static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long n = long.Parse(parts[0]); int bestBase = int.Parse(parts[2]); int best = Beads(n, bestBase); for (int j = 3; j < parts.Length; j++) { int b = int.Parse(parts[j]); int count = Beads(n, b); if (count < best) // 같으면 먼저 적힌 주판을 그대로 둔다 { best = count; bestBase = b; } } sb.Append(bestBase).Append(' ').Append(best).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 行
#include <iostream>using namespace std;// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합).// n을 값으로 받으므로 여기서 줄여도 부른 쪽의 n은 그대로다int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; for (int i = 0; i < q; i++) { long long n; int k, bestBase; cin >> n >> k >> bestBase; int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b; cin >> b; int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } cout << bestBase << ' ' << best << '\n'; } return 0;}
Cmain.c · 36 行
#include <stdio.h>/* 함수 원형: main보다 뒤에 정의하므로, 부르기 전에 생김새를 먼저 알려 준다 */int beads(long long n, int b);int main(void) { int q; scanf("%d", &q); for (int i = 0; i < q; i++) { long long n; int k, best_base; scanf("%lld %d %d", &n, &k, &best_base); int best = beads(n, best_base); for (int j = 1; j < k; j++) { int b; scanf("%d", &b); int count = beads(n, b); if (count < best) { /* 같으면 먼저 적힌 주판을 그대로 둔다 */ best = count; best_base = b; } } printf("%d %d\n", best_base, best); } return 0;}/* n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합) */int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; /* 값으로 받은 복사본만 줄어든다 */ } return total;}
Craykonmain.cray · 32 行
q = 控制台.读行().转数字();循环 (i = 0; i < q; i++){ nums = 控制台.读数字(); n = nums[0]; bestBase = nums[2]; // 함수는 아래에 정의했지만 먼저 부를 수 있다 best = beads(n, bestBase); 循环 (j = 3; j < nums.数量; j++) { count = beads(n, nums[j]); // 같으면 먼저 적힌 주판을 그대로 둔다 如果 (count < best) { best = count; bestBase = nums[j]; } } 控制台.输出(bestBase + " " + best);}// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)beads(n, b){ total = 0; 当 (n > 0) { total += n % b; n = 数学.商(n, b); } 返回 total;}