ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1108. Наследство

Why this code can't got AC?
Послано Romko [Lviv NU] 12 мар 2007 21:37
/....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.
Послано Rumter (2) 1 июл 2008 16:16
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.
Послано Rumter (2) 8 июл 2008 15:37
My wrong is big constant in simple mul.
Now I get AC! :-)