我要招人

去企业版

首页 > 试题广场 >

丛林木马

[编程题]丛林木马

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

朽木裂，雷霆惊，丛林木马怒冲天。

众所周知，如果给你两个数 $a,b$ 要你计算 $a\times b=c$ 的值，你就知道要这么做：把每一位相乘并且乘上它们的 $10^k$ 然后相加，其中 $k$ 表示对应数位的幂次。

有一次，可怜的 ZM 不小心把“相乘”中的所有乘法运算都算成了加法，她想让你帮忙算算，这样算出来的结果是多少？

输入描述:

全文第一行输入一个整数 ，表示数据组数。

每行输入两个正整数 ，表示两个因数。

数据保证 ，其中  表示两个数的位数。

输出描述:

每行输出一个数表示你计算出的答案，为方便输出，你只需要输出最终结果对  取模后的值即可。

示例1

输入

4
12 13
123 456
1314520 5201314
998244353 100000007

输出

说明

对于样例 #1：把每一位拆开并且相加，每一个和统计出来：。



对于样例 #2：



它们的和是：。

算法知识视频讲解

Java

牛客203596504号

我们把数字a从低位向高位列为a[0],a[1],a[2],a[3]……

那么乘法的定义是： $\sum_{i=0}^{|a|-1}\sum_{j=0}^{|b|-1}a[i]*10^i*b[j]*10^j$

换成加法展开就是： $\sum_{i=0}^{|a|-1}\sum_{j=0}^{|b|-1}a[i]*10^i+\sum_{i=0}^{|a|-1}\sum_{j=0}^{|b|-1}b[j]*10^j$

可以看出左式没有j，右式没有i，可以拆除一层累加，得到：
$|b|*\sum_{i=0}^{|a|-1}a[i]*10^i+|a|*\sum_{j=0}^{|b|-1}b[j]*10^j$
再看左式和右式是否熟悉？它就是数a和数b
所以结论：ans=a*|b|+b*|a|

读取数字的时候要注意：
由于原数字过于巨大有10万位，超出任何存储方式，所以要每读一位取模一次。

核心代码：

long[] a = in.nextBigInteger(MOD);
long[] b = in.nextBigInteger(MOD);
long ans = a[0] * b[1] + a[1] * b[0];
sb.append(ans % MOD).append('\n');

private long[] nextBigInteger(long mod) {
    long[] n = new long[2]; // 返回的结果有两个数
    if (buf[i] < '0') i++; // 跳过空格和换行
    while (buf[i] >= '0') {
        n[0] = (n[0] << 3) + (n[0] << 1) + (buf[i++] ^ '0'); // n*10+digit
        n[0] %= mod; // n[0]代表原值取模的结果
        n[1]++; // n[1]代表位数
    }
    return n;
}

发表于今天 03:08:45 回复(0)

提交观点

问题信息

难度：

1条回答 2收藏 15浏览

丛林木马

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题