问题分析

题目要求计算 $n \times 2^k$ 并输出其二进制形式。
其中：

• $n$ 为一个十进制大整数（位数最多可达5000位）。
• $k$ 为一个整数（$0 \leq k \leq 10^5$）。

观察题目可以发现，乘以 $2^k$ 在二进制下相当于将 $n$ 的二进制表示左移 $k$ 位（也就是末尾附加 $k$ 个零）。因此，主要问题转化为将十进制大整数 $n$ 转换为二进制字符串，然后在末尾追加 $k$ 个“0”。

算法思路

1. 转换思路：

   • 利用大数的特性，直接将 $n$ 转换为二进制（在 Python 中可以直接利用内置的任意精度整数，Java 和 C++ 可以使用字符串除 2 的算法来进行转换）。
   • 得到 $n$ 的二进制字符串后，只需在其末尾追加 $k$ 个“0”，即可得到结果。

2. 算法步骤：

   • 步骤1： 输入 $n$ 和 $k$。
   • 步骤2： 将 $n$ 转换为二进制字符串。注意去除前缀 “0b”（如 Python 内置转换的结果）。
   • 步骤3： 在二进制字符串末尾添加 $k$ 个“0”。
   • 步骤4： 输出结果字符串。

复杂度分析

• 时间复杂度：
  将一个 $L$ 位的十进制大数转换成二进制的复杂度大致为 $O(L \times B)$，其中 $B$ 为二进制位数。对于本题 $L \leq 5000$ 且 $B \approx 16610$（最大情况），总体复杂度是可以接受的。此外，追加 $k$ 个字符的操作复杂度为 $O(k)$。
• 空间复杂度：
  存储转换后二进制字符串需要 $O(B + k)$ 的空间，满足题目要求。

代码实现

Python 代码

import sys
sys.set_int_max_str_digits(5005)
# 读取输入
n_str, k_str = input().split()
n = int(n_str)  # 利用 Python 的大数特性直接转换为整数
k = int(k_str)

# 将 n 转换为二进制字符串（去除前缀 '0b'）
binary_n = bin(n)[2:]

# 乘以 2^k 即为在末尾追加 k 个 '0'
result = binary_n + "0" * k

# 输出结果
print(result)

Java 代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 读取输入
        Scanner sc = new Scanner(System.in);
        String nStr = sc.next();
        int k = sc.nextInt();
        sc.close();
        
        // 利用 BigInteger 处理大数
        BigInteger n = new BigInteger(nStr);
        
        // 将 n 转换为二进制字符串
        String binaryN = n.toString(2);
        
        // 乘以 2^k 相当于在二进制字符串后面追加 k 个 '0'
        StringBuilder result = new StringBuilder(binaryN);
        for (int i = 0; i < k; i++) {
            result.append('0');
        }
        
        // 输出结果
        System.out.println(result.toString());
    }
}

C++ 代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 将十进制大数（以字符串表示）转换为二进制字符串
string decToBinary(string n) {
    string binary = "";
    // 当 n 不为 "0" 时进行除 2 操作
    while (n != "0") {
        int carry = 0;
        string temp = "";
        // 对字符串 n 进行逐位除 2
        for (char c : n) {
            int num = carry * 10 + (c - '0');
            temp.push_back((num / 2) + '0');
            carry = num % 2;
        }
        // binary 每次添加余数（即当前最低位），注意需要倒序
        binary.push_back(carry + '0');
        // 去掉 temp 前导的 '0'
        int pos = 0;
        while (pos < temp.size() && temp[pos] == '0') pos++;
        n = (pos == temp.size()) ? "0" : temp.substr(pos);
    }
    // 如果 n 为 "0"，直接返回 "0"
    if (binary == "") return "0";
    // 结果需要翻转，因为最低位在前面
    reverse(binary.begin(), binary.end());
    return binary;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string n;
    int k;
    cin >> n >> k;
    
    // 将 n 转换为二进制字符串
    string binaryN = decToBinary(n);
    
    // 乘以 2^k 即为在末尾追加 k 个 '0'
    binaryN.append(k, '0');
    
    // 输出结果
    cout << binaryN << "\n";
    return 0;
}

题目内容

小歪是一个二进制狂热者，他有两个数字$n$和$2^k$,他想把这两个数字相乘后以二进制的形式输出，但数字太大了，小歪算的头晕眼花，帮帮他！

输入描述

输入两个整数$n,k(1≤n≤10^{5000};0≤k≤10^5)$代表第一个数字和第二个数字的幂

输出描述

输出一个二进制整数，代表乘积的答案。

样例1

输入

12 3

输出

1100000