|
|
back to boardWhy this code can't got AC? /....bigint class...//// .................... bigint a,b,c,temp; a = 2; b = 3; c = a*b; if(n == 1) { cout << '2'; return 0; } cout << "2\n3\n"; for(int i = 3; i <= n; i++) { temp = a*b; c = temp + 1; cout << c << endl; a = c; b = temp; } ................................ //////////////////////////////// What is multiply wrong? I use Karatsub. ubig ubig :: operator * (ubig p) { if (min (n, p.n) < 100) return simple_mul (p); else return karatsuba_mul (p); } ubig ubig :: simple_mul (ubig p) { int i, j; ubig s; for (i = 0; i < n; ++ i) { ubig row; for (j = 0; j < a[i]; ++ j) row = row + p; row = row << i; s = s + row; } while (s.a.size () > 1 && s.a.back () == 0) s.a.pop_back (); s.n = s.a.size (); return s; } ubig ubig :: karatsuba_mul (ubig p) { int k = max (n, p.n) / 2; ubig a = (*this).last (k); ubig b = (*this) >> k; ubig c = p.last (k); ubig d = p >> k;
ubig ac = a * c; ubig bd = b * d; ubig abcd = (a + b) * (c + d);
ubig res = ((abcd - ac - bd) << k) + (bd << 2 * k) + ac; return res; } I get TL1. I dont understand :-(. Re: What is multiply wrong? I use Karatsub. My wrong is big constant in simple mul. Now I get AC! :-) |
|
|