关于一个运算优化的问题
精品文章！是一个ACM的题,地址如下。http://acm.timus.ru/problem.aspx?space=1&num=1318
大概意思就是给出5000个左右的128位的整数，求：
http://acm.timus.ru/image/get.aspx/31e107d2-fdcc-4d67-8faf-285152fbf650
我也作了不少优化（包括分治），虽然可以过，但似乎同别人的算法似乎还有不小的差距，请高手们帮我想想还有什么好的方法没有！
我想用二叉树可能会好一点，但思路还不太清晰。 $A_k, A_j$什么关系，可以相等么？
首先排序么？
我看不懂他的意思 论坛有计算$log_10$的代码 可以相等,初始是无序的,不过可以排序!
另外忘了说明了,LOG10之后,只保留整数部分就可以!
原帖由 无心人 于 2009-3-12 14:46 发表 http://bbs.emath.ac.cn/images/common/back.gif
$A_k, A_j$什么关系，可以相等么？
首先排序么？ 是$A_k, A_j$遍取所有的可能？
即如果有100个，则生成10000个XOR值？？ 原帖由 无心人 于 2009-3-12 14:50 发表 http://bbs.emath.ac.cn/images/common/back.gif
是$A_k, A_j$遍取所有的可能？
即如果有100个，则生成10000个XOR值？？
是这个意思!然后取log10的整数部分,都加在一起! 按照我目前的理解
如果无序，且遍取所有可能
是无需排序的
只要进行一次遍历就可以了
大概1000万次的XOR
然后求$log_10$
这个是整数算法
应该能在1秒左右完成 5000 的128位值还不需要用文件操作
直接能一次读取到内存
然后是个
for (i = 0; i < N - 1; i ++)
for (j = i + 1, j < N; j ++)
的两重循环 就是测试128位数字的$ log_10$麻烦些
不过， 用个Cache，加上几个判断就能做好
完全的整数运算
很快的
看论坛有求32位的代码 我说一下我现在用的方法吧!先求出10^0 - 10 ^ 38，并分别计算最高位所在的位置。
对A数组排个序，然后只需计算A同比A小的数logXor就可以了，最后的结果*2
在计算过程中，先求出5000个数的最高位，并分类，如果最高位m高于10^n,且低于10^n+1，那么这个数同最高位小于m的数进行Xor并取log10后的结果，都是n，因此有些数是可以批量算的（但所占比例不是很大）。
基本上就是做了这些优化。