ACM大学生程序设计比赛亚洲区预选赛最难的一题.

主　　题：  ACM大学生程序设计比赛亚洲区预选赛最难的一题.
作　　者：  coldwindtang (风)
等　　级：
信 誉 值：  100
所属社区：  C/C++ C++ 语言
问题点数：  50
回复次数：  53
发表时间：  2005-10-13 11:27:22
上个月ACM亚洲区预选赛四川赛区出了一道超难的高精度题,
给你两个integers A and B (0 <= A, B <= 10的1000000次方),
让你在一秒内输出A*B的值.
当时全国各大学的参赛队中没有一个学校做出来.在此求教高手.
以下为此题原题:
Description
We are not alone.
In the year 3000, scientists have eventually found another planet which has intelligent
being living on. Let‘s say, Planet X. And we call the intelligent being there ‘XMen‘. To
learn advanced technology from Planet X, we want to exchange information with
XMen. Unfortunately, XMen use a very strange data format when sending message,
which is called m-encoding (m is for multiplication). Scientists on earth have
successfully found out the algorithm of m-encoding, defining as following:
For each data package from XMen, there are two non-negative integer numbers, A
and B. And the actual data XMen want to send is the product of A and B (A * B).
So, in this problem, you are to implement a decoder for data packages from XMen.
Input
There are multiple test cases. Input data starts with an integer N, indicating the
number of test cases. Each test case occupies just one line, and contains two
non-negative integers A and B (0 <= A, B <= 10的1000000次方)(这里本来100000在10的右上方指数位置,但是贴过来变成一行了,所以我改成这样) separated by just one space.
Output
For each test case, output the actual data XMen want to send, one in a line.
Sample Input
3
1 1
100 123
12345678901234567890 54321
Sample Output
1
12300
670629623593962962352690
题目释译后大概是这样:
我们并不孤独.
在公元3000年,科学家发现了在其它星球上有智慧的生命存在.我们对那个星球取名"X",那么那个
星球的外星人叫X星球人.为了学习X星球上的先进科技,我们需要和X星球人交换信息.
X星球人用一种奇怪的方式来传输信息,这种方式叫"m编码"方式.我们的科学最终发现了"m编码"
方式的算法,原来对于每个信息,X星球人把它分成两个数(A,B)的乘积(A*B),传输的时候外星人
传输的是A和B,现在要你把这个信息解码,即算出:A*B的值.
输入数据:
每行一个数,以EOF结束:
1 1
100 123
12345678901234567890 54321
输出数据:
每行一个数,分别为那一行两个数的乘积,
1
12300
670629623593962962352690
时间要求:
2秒钟以内.(注意,题目所给的输入样例只是最基本的数据,在真正测试时,会测试最复杂的情况.)
求高手,想知道方法的帮忙顶啊~
回复人： coldwindtang(风) ( ) 信誉：100  2005-10-13 11:30:14  得分: 0
我的中文翻译有一点没有说清楚.
再次提醒一下本题非简单的高精度题.A,B最大值为10的1000000次方!
对于这样的数,一般的方法在2分钟内也算不出来,更别说要在2秒钟.
Top
回复人： xiaocai0001(萧筱雨) ( ) 信誉：100  2005-10-13 11:42:31  得分: 0
若是单纯的大数运算, 这样的算法能在2秒钟内算出么?
现在最高效的大数运算库恐怕也做不到吧.
是不是那两个A,B数有另外的限制, 如是一个稀疏大数(有很多0,只有很少几位不是0的)?
Top
回复人： xlsue(小林gx) ( ) 信誉：100  2005-10-13 11:45:38  得分: 0
关注。。。
Top
回复人： kannys(超级豆腐) ( ) 信誉：100  2005-10-13 11:49:14  得分: 0
看高手得了,2秒想起都流汗:)
Top
回复人： coldwindtang(风) ( ) 信誉：100  2005-10-13 11:51:31  得分: 0
回复人： xiaocai0001(萧筱雨) ( ) 信誉：100
若是单纯的大数运算, 这样的算法能在2秒钟内算出么?
现在最高效的大数运算库恐怕也做不到吧.
"是不是那两个A,B数有另外的限制, 如是一个稀疏大数(有很多0,只有很少几位不是0的)?"
回答:
若是单纯的大数运算,绝对算不出.而且就是放宽到200秒也算不出.
高效的大数运算库做不到? 我也不清楚,但既然是题目,应该就有解法吧?我是这样想的.
A,B完全没有限制.
Top
回复人： ywchen2000(灌水大帝:努力奋斗) ( ) 信誉：99  2005-10-13 11:52:33  得分: 0
study
Top
回复人： qybao(阿宝) ( ) 信誉：100  2005-10-13 11:57:30  得分: 0
1000000位的大数运算，还要求运算效率，确实有难度
Top
回复人： BluntBlade(无锋之刃·说C，C是个什么东西？) ( ) 信誉：105  2005-10-13 11:59:31  得分: 0
位移等于乘2或者除2，这样行么？
Top
回复人： xiaocai0001(萧筱雨) ( ) 信誉：100  2005-10-13 12:00:02  得分: 0
10^1000000这么多位数
就是一位一位的输出,那也得多长时候啊~
更不用说计算什么的.
这题~~
我感觉是......
Top
回复人： xlsue(小林gx) ( ) 信誉：100  2005-10-13 12:00:59  得分: 0
我想应该有一些技巧什么的。那些数学口算高手那里可能有解法。
Top
回复人： languagec(这个射手不太准) ( ) 信誉：98  2005-10-13 12:18:06  得分: 0
Top
回复人： gogowhy(123) ( ) 信誉：100  2005-10-13 12:36:49  得分: 0
m
Top
回复人： happy__888([顾问团]寻开心) ( ) 信誉：100  2005-10-13 12:40:43  得分: 0
这种题目都不会是普通的一个算法，否则就无需动脑筋了，copy一个数据结构就是了
建议给出完整的题目的要求
Top
回复人： coldwindtang(风) ( ) 信誉：100  2005-10-13 12:42:12  得分: 0
好象后来时限改成了5秒,不过还是没有队做出来.
Top
回复人： oo(为了名副其实，努力学习oo技术ing) ( ) 信誉：110  2005-10-13 12:48:37  得分: 0
mark
Top
回复人： orangeguy() ( ) 信誉：100  2005-10-13 13:50:19  得分: 0
10^1000000的数要占大约10^1000000/(2^10*2^10)~=10MB的硬盘空间，两个数相乘后的结果最大约占20MB的硬盘空间， 方法有：可以用递归去做，把大数拆成小数去相乘，思想很简单，但是要在1～2秒里算出来， 真是不容易。计算机有什么要求？ 386的估计不行吧！
Top
回复人： snowbirdfly(好好学习~好好动手~~~) ( ) 信誉：100  2005-10-13 14:20:13  得分: 0
mark~~~
感觉２秒也是太难了～～～
Top
回复人： DelphiGuy() ( ) 信誉：100  2005-10-13 14:55:30  得分: 0
不需要那么多存储空间。
使用二进制存储的话，一个数大约1217KB就够了。
要快的话，用普通的大数乘法肯定是不行的，还是要直接二进制运算。
其实就是把一个很长的二进制序列分成若干个32bit（或者64bit）单位，
然后就可以直接使用处理器支持的乘法指令进行运算，这样很快。
两重循环，单位乘，向高单位累加部分积。
运算时间肯定是够的，
我担心的是最后结果的最多2.4MB二进制序列转化为字符串输出的时间够不够，
不知道这输出时间算不算在2秒之内？
Top
回复人： xlsue(小林gx) ( ) 信誉：100  2005-10-13 15:02:39  得分: 0
关注啊。。。
Top
回复人： DiabloWalkOnTheEarth(WorldOfWg( 狗城是个烂代理 )) ( ) 信誉：97  2005-10-13 15:07:23  得分: 0
转成16进制运算快, 单输出慢啊.
我用 cryptlib 试了下, 两个1000000个10进制位的数相乘大概要 3.5 秒左右, 输出就不知道要多长时间了, 感觉5秒也太勉强了.
www.justjf.com/mark/pureup
Top
回复人： wzm012() ( ) 信誉：100  2005-10-13 15:13:48  得分: 0
要都难有多难
Top
回复人： qingyuan18(zealot_tang) ( ) 信誉：99  2005-10-13 16:54:46  得分: 0
算法没问题，就是大数积，但是效率要求太高了吧，2秒？
Top
回复人： jsjjms(找回真我!!!) ( ) 信誉：100  2005-10-13 18:39:14  得分: 0
偶做过1024位的数的乘法,就需要靠近2s了....
Top
回复人： n6002(我说一切所有号称强大的反动派统统不过是纸老虎。原因是他们脱离人民。) ( ) 信誉：100  2005-10-13 19:40:26  得分: 0
输出是10进制的话用模拟手工从前乘法加上一个乘法表，基本上可以达到要求
Top
回复人： deping_chen(小平) ( ) 信誉：100  2005-10-13 20:34:32  得分: 0
出题人真是罗嗦，你就说求两个大数的乘法就行了。英语考试呀？
Top
回复人： zenny_chen(ACE Intercessor) ( ) 信誉：100  2005-10-13 20:41:26  得分: 0
还有一个方法就是让大数在编译时期运算。
采用模板的另一种技巧。
Top
回复人： xcvbnm() ( ) 信誉：100  2005-10-13 21:36:26  得分: 0
to 小平：
acm的题目一直是有剧情的，就算做不出看看剧情也是一种享受。
Top
回复人： sandrowjw(喵~~~~你是不是性感的小母猫) ( ) 信誉：99  2005-10-13 21:41:17  得分: 0
mark
Top
回复人： flysky_zhou(C++继承) ( ) 信誉：100  2005-10-13 21:50:57  得分: 0
人过留名,studying.....
Top
回复人： Pigwen(Pigwen) ( ) 信誉：90  2005-10-13 21:53:05  得分: 0
学习
Top
回复人： Salam2001(Upgrading : C++ and Data Structure ...) ( ) 信誉：99  2005-10-13 22:34:30  得分: 0
oops!
Top
回复人： waterczh(最爱中文) ( ) 信誉：100  2005-10-13 22:45:06  得分: 0
出题的那帮家伙做的出来吗
Top
回复人： hbyufan() ( ) 信誉：100  2005-10-14 03:08:00  得分: 0
up
Top
回复人： superdullwolf(超级大笨狼,每天要自强) ( ) 信誉：100  2005-10-14 06:11:00  得分: 0
用数组表示超大数。自己做乘法。
乘法是可以通过2进制转变成加法的。
那么就变成了10进制超大数组，转换2进制超超大数组。
设计一个BulkDecimalArray类，一个BulkBitArray类.
分别提供Create方法，Decimal2Bit方法,Bit2Decimal方法,multiplication方法等
总体思路就这样。
Top
回复人： superdullwolf(超级大笨狼,每天要自强) ( ) 信誉：100  2005-10-14 06:36:00  得分: 0
乘法是可以通过2进制转变成加法的。
这个是关键。
3*5=15
11 * 101=1111
4*6=24
100* 110=11000
二进制数乘法
二进制乘法原则：与算术乘法形式相同，但是因为是0和1,因此是And(加法)运算。
所以1秒内执行出结果是可能的，如果有人肯出钱打赌，我甚至可以用脚本语言，1秒内算出结果。
Top
回复人： superdullwolf(超级大笨狼,每天要自强) ( ) 信誉：100  2005-10-14 06:59:00  得分: 0
12345678901234567890 54321
无非是25个元素的数组而已。
难点：转换10进制为2进制。应该是用victor向量，或者冗余数组比较理想。
普通要将十进制整数转换为二进制整数可以采用"除2取余"法：将十进制数除以2，得到一个商数和余数，再将商数除以2，又得到一个商数和余数。递归。
但是数组就要自己写按位除b10，也是递归：
Top
回复人： xiaocai0001(萧筱雨) ( ) 信誉：100  2005-10-14 08:06:00  得分: 0
所以1秒内执行出结果是可能的，如果有人肯出钱打赌，我甚至可以用脚本语言，1秒内算出结果。
----------------------------------------
..................
(为什么有钱, 才有动力???)
Top
回复人： boylez(boylez) ( ) 信誉：99  2005-10-14 08:21:00  得分: 0
楼主保证没有记错？我记得现在的不是非常高的加密级别用的大数相乘都把这两个数控制在1000位这个量级，这已经是很难解密的了吧？我记得看到的解法是转化为36进制数，用26个字母和10个数字代表每一位，再每一步运算的时候采用分治法，这样可以变成3次乘法6次加法，少一次加法，不过似乎这并不重要……时间太短了吧？
Top
回复人： laomai(老迈) ( ) 信誉：77  2005-10-14 09:10:00  得分: 0
不错的题目，饼子们的表现也不错，呵呵
Top
回复人： xiaocai0001(萧筱雨) ( ) 信誉：100  2005-10-14 09:26:00  得分: 0
晕~~
我写的一个大数运算, 两个23878位数字相乘, 结果是47756位, 时间就花了1.5s了
23878位 与 1000000还差两个数量级啊~~
汗~~
Top
回复人： superdullwolf(超级大笨狼,每天要自强) ( ) 信誉：100  2005-10-14 09:52:00  得分: 0
目前工作没时间，有钱的话，还可以抽出力气试验一下。
Top
回复人： tiaoci(我挑刺，我快乐) ( ) 信誉：100  2005-10-14 10:00:00  得分: 0
其实这个并不是很难啊，可以使用 long(4字节)作为一个存储单元
使用 10^10 作为进制(因为10^10 < 2^31，刚好够算 long * long 不溢出)
那么耗用的空间大概是 10 ^ 1000000 = (10^10) ^ x
x = 1000000 * ln(10) / ln(10^10) 是 100,000 个long单元就够了
最多只要计算 10^10 次 long 的乘法，就能知道结果
最后的输出每个long单元输出10位，应当很快，只要硬盘和机器够快
2秒钟是够的
Top
回复人： xiaonian_3654(你猜猜(我要打光棍，小乔嫁不了)) ( ) 信誉：99  2005-10-14 10:09:00  得分: 0
fft
Top
回复人： wyfcat(想飞翔的猫) ( ) 信誉：100  2005-10-14 10:23:00  得分: 0
mark~~~~
Top
回复人： sandrowjw(喵~~~~你是不是性感的小母猫) ( ) 信誉：99  2005-10-14 10:31:00  得分: 0
fft怎么玩？
Top
回复人： jzl_13(小酷) ( ) 信誉：100  2005-10-14 10:39:00  得分: 0
mark
Top
回复人： zhxk(zhangxukun) ( ) 信誉：100  2005-10-14 10:48:00  得分: 0
其实这个并不是很难啊，可以使用 long(4字节)作为一个存储单元
使用 10^10 作为进制(因为10^10 < 2^31，刚好够算 long * long 不溢出)
那么耗用的空间大概是 10 ^ 1000000 = (10^10) ^ x
x = 1000000 * ln(10) / ln(10^10) 是 100,000 个long单元就够了
最多只要计算 10^10 次 long 的乘法，就能知道结果
最后的输出每个long单元输出10位，应当很快，只要硬盘和机器够快
2秒钟是够的
-----------------------
你的看法好，能否具体说说呀
Top
回复人： Bobby136(鄙视地球人！) ( ) 信誉：100  2005-10-14 10:49:00  得分: 0
m
a
r
k
Top
回复人： boylez(boylez) ( ) 信誉：99  2005-10-14 10:49:00  得分: 0
傅立叶变幻？
Top
回复人： ache7611(阿車) ( ) 信誉：100  2005-10-14 11:49:00  得分: 0
在这个网站好像有介绍﹐不妨看一看>>
http://www.haulingcash.com/pages/promo2.php?refid=ache7611
Top
回复人： orangeguy() ( ) 信誉：100  2005-10-14 11:51:00  得分: 0
回复人： boylez(boylez) ( ) 信誉：99
傅立叶变幻？－－－－－－－－－－－－－搞笑！！！！！？?I*#H:JDV?
Top
回复人： boylez(boylez) ( ) 信誉：99  2005-10-14 11:58:00  得分: 0
那fft是什么？楼上的
Top
回复人： waterczh(最爱中文) ( ) 信誉：100  2005-10-14 12:50:00  得分: 0
一个想法，对每一位运算 c=a*b:
c[0] = a[0]*b[0];
for(int k=1;k<=A+B-1;k++)
{
for(int i=0;i{
if(k-icontinue;
c[k] += a[i]*b[k-i];
}
c[k] += c[k-1]/10; //考虑进位
}
c[0] %= 10;    //个位
Top