具体资料网上有，自己查一下看：）
下面简略说一下分制，估计大多数都也都知道的：
用分制比如就把乘数分为两部分（可以按照高位，低位分也可以按照奇数位偶数位分）
X=A*2^k+B;Y=C*2^k+D
然后有X*Y=A*B*2^（2k）+(A*D+B*C)*2^k+C*D;
这里只要计算3次n/2（设原来的X和Y都是n位的）乘法
K1=A*B;
K2=C*D;
K3=(A+B)*(C+D)-K1-K2=A*D+B*C;
时间复杂度就是T(n)=3T(n/2)+O(n);
就是n^lg3的复杂度

• Re:前者用分制，比较简单；后者用傅立叶变换 (332) daizisheng 2003-10-18 20:08:49
  • 我数据给的少而已，用分制当然会更快啊 (63) hawk 2003-10-18 20:30:19
    • PKU的服务器好快啊 我的C程序居然能过：) (0) atlas_of_rruucc 2004-07-03 23:06:48
      • 为什么会不能过呢？ (0) hawk 2004-07-04 12:13:41
        • 在我的电脑上它运行了9S！ (0) atlas_of_rruucc 2004-07-04 21:43:27