题解

题意是要求 $n$ 在 $m$ 进制中有多少个 $1$。

按照题意暴力进行模拟就行，总体复杂度为 $O(35 \times \log(n))$

AC代码

• CPP

  #include <iostream>
  #include <string>
  #include <algorithm>
  using namespace std;
  
  int main() {
      int n;
      cin >> n;
      
      int ans = 0;
      for (int i = 2; i <= 36; i++) {
          int t = n;
          int cnt = 0;
          while (t) {
              int z = t % i;
              // 统计z转为字符串后包含'1'的个数
              cnt += to_string(z).count('1'); 
              t /= i;
          }
          ans = max(ans, cnt);
      }
      cout << ans << endl;
      return 0;
  }
  

• Python

  n = int(input())
  ans = 0
  for i in range(2, 37):  # 遍历进制i从2到36
      t, cnt = n, 0
      while t:
          z = t % i       # z是n在i进制下的最低位
          cnt += str(z).count('1')  # 统计z转为字符串后包含'1'的个数
          t //= i         # n整除i,相当于把n在i进制下右移一位
      ans = max(ans, cnt)
  print(ans)
  

• Java

  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          
          int ans = 0;
          for (int i = 2; i <= 36; i++) {
              int t = n;
              int cnt = 0;
              while (t > 0) {
                  int z = t % i;
                  // 统计z转为字符串后包含'1'的个数
                  cnt += String.valueOf(z).chars().filter(ch -> ch == '1').count();
                  t /= i;
              }
              ans = Math.max(ans, cnt);
          }
          System.out.println(ans);
      }
  }
  

题目描述

我们已经知道 2 进制到 10 进制表示方法，与 16 进制类似，我们考虑 11~36 进制，即用 a 代表 10 ，b 代表 11 等。

我们想知道给定一个 10 进制数 $n$，其在 2 ~36 进制下的所有进制表示中，含有 1 的数量最多是多少。

比如 4 在二进制下表示为 $(100)_2$，只有一个 1。

输入描述

在一行上输入一个整数 $n$（$1 \leq n \leq 3 \times 10^5$）代表给定的十进制数。

输出描述

在一行上输出一个整数表示答案。

示例 1

输入

4

输出

2

说明

在 3 进制下，4 为 $(11)_3$，有两个 1 。

示例 2

输入

11

输出

3

说明

在 2 进制下，11 有三个 1。