#include <iostream>
 
int jacobi(int q, int p)
{
    int s = 0, u = q, v = p;
    int r, k, t;
    do{
        // Вычисляем r - наименьший положительный остаток при делении u на v
        r = u % v;
        // Вычисляем целое r >= 0 и нечетное t: r = t * 2^k
        k = t = 0;
        while(r & 0x1 == 0) // Пока r делится на 2
        {
            k++;    // Выделяем степень двойки в числе r
        }
        // Используем t для вычисления 2^k при помощи битовых сдвигов
        t = 1;  // Единицу умножаем на степень двойки (следующая строка)
        t <<= k;
        //t = r / t;  // Разделили r на 2^k, теперь в t результат этого деления
        t = r / t;  // Разделили r на 2^k, теперь в t результат этого деления
        s = (s + k * (v*v - 1) / 8 + (t - 1) * (v - 1) / 4) % 2;
        if(t == 1)
            return (s == 1) ? -1 : 1;
        u = v;
        v = t;
    }while(t >= 3);
}
 
int main() {
    std::cout << jacobi(184, 347) << std::endl;
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKaW50IGphY29iaShpbnQgcSwgaW50IHApCnsKICAgIGludCBzID0gMCwgdSA9IHEsIHYgPSBwOwogICAgaW50IHIsIGssIHQ7CiAgICBkb3sKICAgICAgICAvLyDQktGL0YfQuNGB0LvRj9C10LwgciAtINC90LDQuNC80LXQvdGM0YjQuNC5INC/0L7Qu9C+0LbQuNGC0LXQu9GM0L3Ri9C5INC+0YHRgtCw0YLQvtC6INC/0YDQuCDQtNC10LvQtdC90LjQuCB1INC90LAgdgogICAgICAgIHIgPSB1ICUgdjsKICAgICAgICAvLyDQktGL0YfQuNGB0LvRj9C10Lwg0YbQtdC70L7QtSByID49IDAg0Lgg0L3QtdGH0LXRgtC90L7QtSB0OiByID0gdCAqIDJeawogICAgICAgIGsgPSB0ID0gMDsKICAgICAgICB3aGlsZShyICYgMHgxID09IDApIC8vINCf0L7QutCwIHIg0LTQtdC70LjRgtGB0Y8g0L3QsCAyCiAgICAgICAgewogICAgICAgICAgICBrKys7ICAgIC8vINCS0YvQtNC10LvRj9C10Lwg0YHRgtC10L/QtdC90Ywg0LTQstC+0LnQutC4INCyINGH0LjRgdC70LUgcgogICAgICAgIH0KICAgICAgICAvLyDQmNGB0L/QvtC70YzQt9GD0LXQvCB0INC00LvRjyDQstGL0YfQuNGB0LvQtdC90LjRjyAyXmsg0L/RgNC4INC/0L7QvNC+0YnQuCDQsdC40YLQvtCy0YvRhSDRgdC00LLQuNCz0L7QsgogICAgICAgIHQgPSAxOyAgLy8g0JXQtNC40L3QuNGG0YMg0YPQvNC90L7QttCw0LXQvCDQvdCwINGB0YLQtdC/0LXQvdGMINC00LLQvtC50LrQuCAo0YHQu9C10LTRg9GO0YnQsNGPINGB0YLRgNC+0LrQsCkKICAgICAgICB0IDw8PSBrOwogICAgICAgIC8vdCA9IHIgLyB0OyAgLy8g0KDQsNC30LTQtdC70LjQu9C4IHIg0L3QsCAyXmssINGC0LXQv9C10YDRjCDQsiB0INGA0LXQt9GD0LvRjNGC0LDRgiDRjdGC0L7Qs9C+INC00LXQu9C10L3QuNGPCiAgICAgICAgdCA9IHIgLyB0OyAgLy8g0KDQsNC30LTQtdC70LjQu9C4IHIg0L3QsCAyXmssINGC0LXQv9C10YDRjCDQsiB0INGA0LXQt9GD0LvRjNGC0LDRgiDRjdGC0L7Qs9C+INC00LXQu9C10L3QuNGPCiAgICAgICAgcyA9IChzICsgayAqICh2KnYgLSAxKSAvIDggKyAodCAtIDEpICogKHYgLSAxKSAvIDQpICUgMjsKICAgICAgICBpZih0ID09IDEpCiAgICAgICAgICAgIHJldHVybiAocyA9PSAxKSA/IC0xIDogMTsKICAgICAgICB1ID0gdjsKICAgICAgICB2ID0gdDsKICAgIH13aGlsZSh0ID49IDMpOwp9CgppbnQgbWFpbigpIHsKICAgIHN0ZDo6Y291dCA8PCBqYWNvYmkoMTg0LCAzNDcpIDw8IHN0ZDo6ZW5kbDsKICAgIHJldHVybiAwOwp9