A*B 问题

女爷i 2022-05-30 02:54 157阅读 0赞

## A\*B 问题 ##

问题描述

计算最多20010位十进制正整数A和B的乘积A\*B。

输入样例

1259

输出样例

10072

<table style="color:rgb(68,68,68);font-size:13px;line-height:25px;max-width:100%;border-spacing:0px;width:1615px;margin-bottom:20px;background-color:transparent;"> 
 <thead> 
  <tr> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">&nbsp;</th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
   <th style="padding:4px;line-height:20px;vertical-align:bottom;border-top-width:0px;">额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185);" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom;border:0px;height:16px;padding-left:3px;width:16px;"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">测试用例 1</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71118&amp;test=90849&amp;type=in&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">1259↵</span></li> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">8↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);"><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=71118&amp;test=90849&amp;type=out&amp;download=0" style="color:rgb(67,142,185);font-size:9pt;" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top;padding:0px 5px 0px 0px;width:10em;height:10em;"> 
     <ol style="margin-bottom:0px;margin-left:2.5em;"> 
      <li style="font-family:Consolas, 'Courier New', Courier, mono, serif;margin:0px;padding:0px;"><span style="margin:0px;padding:0px;white-space:nowrap;background-color:rgb(211,211,211);">10072↵</span></li> 
     </ol> 
    </div></td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">1秒</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">64M</td> 
   <td style="padding:4px;line-height:20px;vertical-align:middle;background-color:rgb(249,249,249);">0</td> 
  </tr> 
 </tbody> 
</table>

Java版大整数类

import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner sc=new Scanner(System.in);
    		String str1=sc.nextLine();
    		String str2=sc.nextLine();
    		BigInteger x1=new BigInteger(str1);
    		BigInteger x2=new BigInteger(str2);
    		System.out.println(x1.multiply(x2));
    	}
    
    }

C++:O(n^2)

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string>
    using namespace std;
    int A[40025];
    int B[40025];
    int ans[40025];//ans[0]用来存储答案的位数
    string s;
    int main()
    {
    	int i = 1; int j = 1;
    	string str1;
    	string str2;
    	cin >> str1; cin >> str2;
    	int lenA = str1.length();
    	int lenB = str2.length();
    	for (; i <= lenA; i++)
    		A[i] = str1[lenA - i]-'0';
    	for (; j <= lenB; j++)
    		B[j] = str2[lenB - j]-'0';
    	ans[0] = 1;
    	for (int i = 1; i <= lenA; i++)
    	{
    		for ( j = 1; j <= lenB; j++)
    		{
    			ans[i + j-1] += A[i] * B[j];
    		}
    	}
    	for (int i = 1; i <= lenA+lenB; i++)
    	{
    		ans[i + 1] += ans[i] / 10; ans[i] %= 10;
    	}
    	if (ans[lenA + lenB]) ans[0] = lenA + lenB;
    	else
    		ans[0] = lenA + lenB - 1;
    	for (int k = ans[0]; k >= 1; k--)
    		printf("%d", ans[k]);
    	printf("\n");
    	
    	return 0;
    }