Алгоритм проверки равенства перемножения
Подскажите, пожалуйста, алгоритм проверки следующего равенства
a[0]*a[1]*...*a[n-1] = b[0]*b[1]*...*b[m-1]
Количество операций должно быть не более O(n*m).
Каждый элемент массивов a и b типа long long, согласно алгоритму не должно быть переполнений типа.
Ответы (4 шт):
Проходим каждый элемент массива a и с данным элементом проходим каждый элемент массива b. Вычисляем их НОД (наибольший общий делитель) и сокращаем оба элемента.
Но сначала вычисляем знак умножений и дальше работать будем только с положительными числами.
Умножения будут равны, если все числа останутся равными единице.
int знакA = знак ( a )
int знакB = знак ( b )
если знакA != знакB то
return False
если знакA == 0 то
return True
for ai из a do {
for bi из b do {
nod = НОД ( ai , bi )
ai /= nod
bi /= nod
если ai == 1 то
break
}
если ai != 1 то
return False
}
return True
int знак ( a ) {
зн = +1
for ai из a do {
если ai == 0 то
return 0
если ai < 0 то {
зн = - зн
ai = - ai
}
}
return зн
}
Задачу можно решить за O((m+n)*sqrt(maxvalue)) (множитель зависит от размера чисел, суть константа, но большая).
Каждое число раскладываем в произведение степеней простых множителей, складываем степени для всех чисел в списке, сравниваем наборы для двух списков. Демонстрация на Питоне.
Содержимое словаря после прохода первого списка:
{1000000007: 1, 2: 10, 3: 5, 5: 2, 7: 1, 11: 1})
from collections import defaultdict
def compareproducts(a, b):
da = defaultdict(int)
for F in a:
d = 2
while d*d <= F:
m = 0 #степень множителя
while F % d == 0:
m += 1
F //= d
if m:
da[d] = da[d] + m
d += 2 if d > 2 else 1 #после двойки идём по нечётным
if F > 1:
da[F] = da[F] + 1
for F in b:
d = 2
while d*d <= F:
m = 0
while F % d == 0:
m += 1
F //= d
if m:
da[d] = da[d] - m
d += 2 if d > 2 else 1
if F > 1:
da[F] = da[F] - 1
for v in da.values(): #все нули - произведения равны
if v:
return(False)
return True
print(compareproducts([1000000007,479001600],[100000000700, 66528, 72]))
>> True
Ставлю на GCD. При таких значениях (размер-то long long) факторизация работает просто ужасно. Тем более что при GCD есть микрооптимизация — первое же число, которое оказывается после прохода по элементам второго произведения, не равным 1, дает основания закончить проверку. В случае же факторизации надо раскладывать все числа.
Впрочем, может, я где-то что-то не так написал? Тогда перепроверьте и поправьте...
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <random>
#include <chrono>
class muTimer
{
using Clock = std::chrono::high_resolution_clock;
bool active = false;
Clock::duration duration_;
Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
muTimer(const muTimer&) = delete;
muTimer& operator=(const muTimer&) = delete;
public:
using ns = std::chrono::nanoseconds;
using mks = std::chrono::microseconds;
using ms = std::chrono::milliseconds;
muTimer() { reset(); start(); }
~muTimer() = default;
muTimer& reset()
{
duration_ = std::chrono::nanoseconds(0);
active = false;
return *this;
}
muTimer& start()
{
if (!active)
{
start_ = Clock::now();
active = true;
}
return *this;
}
muTimer& stop()
{
if (active)
{
stop_ = Clock::now();
duration_ += stop_ - start_;
active = false;
}
return *this;
}
template<typename T = mks>
unsigned long long duration()
{
return static_cast<unsigned long long>
(std::chrono::duration_cast<T>(stop_-start_).count());
}
};
using namespace std;
default_random_engine rgen{random_device{}()};
// 1: definitery equals, 0: definitely different, -1: who knows?
int diff(const vector<long long>& a, const vector<long long>& b)
{
int asign = 1, bsign = 1;
for(auto n: a)
if (n == 0) { asign = 0; break; }
else if (n < 0) asign = -asign;
for(auto n: b)
if (n == 0) { bsign = 0; break; }
else if (n < 0) bsign = -bsign;
if (!asign && !bsign) return 1;
if (asign * bsign == 1) return -1;
return 0;
}
bool equalPrime(const vector<long long>& a, const vector<long long>& b)
{
int d = diff(a,b);
if (d == 0) return false;
else if (d == 1) return 1;
unordered_map<long long,int> z;
for(auto n: a)
{
if (n < 0) n = -n;
while(n%2 == 0) { z[2]++; n /= 2; }
for (long long j = 3; j*j <= n; j += 2)
while(n%j == 0) { z[j]++; n /= j; }
if (n != 1) z[n]++;
}
for(auto n: b)
{
if (n < 0) n = -n;
while(n%2 == 0) { z[2]--; n /= 2; }
for (long long j = 3; j*j <= n; j += 2)
while(n%j == 0) { z[j]--; n /= j; }
if (n != 1) z[n]--;
}
for(auto x: z) if (x.second) return false;
return true;
}
bool equalGCD(vector<long long> a, vector<long long> b)
{
int d = diff(a,b);
if (d == 0) return false;
else if (d == 1) return 1;
for(auto& i: a) if (i < 0) i = -i;
for(auto& i: b) if (i < 0) i = -i;
for(int i = 0; i < a.size(); ++i)
{
for(int j = 0; j < b.size(); ++j)
{
if (long long g = gcd(a[i],b[j]); g != 1)
{
a[i] /= g;
b[j] /= g;
}
}
if (a[i] != 1) return false;
}
for(auto i: a) if (i != 1) return false;
for(auto i: b) if (i != 1) return false;
return true;
}
int main(int argc, char * argv[])
{
vector<long long> a, b;
uniform_int_distribution uint_d(0ll,200000000000000ll);
for(int j = 0; j < 100; ++j)
{
a.push_back(uint_d(rgen));
b.push_back(uint_d(rgen));
}
bool p, q;
{
muTimer mt;
q = equalGCD(a,b);
mt.stop();
cout << "equalGCD : " << mt.duration<>() << " mks\n";
}
{
muTimer mt;
p = equalPrime(a,b);
mt.stop();
cout << "equalPrime: " << mt.duration<>() << " mks\n";
}
cout << p << q << endl;
}
Исправил с учетом замечаний Stanislav Volodarskiy. См. код тут — генерация файла с простыми числами и проверка равенства произведений. Кому интересно, поиграйтесь.
Кое-какие мысли по задаче.
Ответ на вопрос
Так как запрошена сложность O(nm), то вычисляем НОД для всех пар и сокращаем множители на эти НОДы. Если остались все единицы, есть равенство. Алфавит конечный, считаем что НОД вычисляется за константу. Это решение уже привёл Harry. Ничего нового я не скажу.
"Быстрый" алгоритм
Опять таки, алфавит конечный - значит разложение на простые делается за константу. Раскладываем все множители на простые, сравниваем степени при простых. Если равны все степени, то равны и произведения. Работает за линейное время - O(n + m). Но константа тут неприятная.
Примем что, числа 64 бита со знаком. Максимальное значение 263. Для разложения потребуются простые до примерно трёх миллиардов (√(263)). А именно 146144318 простых чисел. В худшем случае каждое число нужно будет делить 146 миллионов раз. Есть различные оптимизации, но есть и плохой случай, которые эти оптимизации не берут.
Наберём 2N простых чисел не далеко от √(263). Превышать значение нельзя. Разобьем их на пары и составим из произведений в парах первый массив. Другое разбиение на пары того же набора чисел даст второй массив. Два разбиения можно так устроить, что равных чисел в массивах не будет. Это нужно чтобы не работала оптимизация "выкинем равные".
Чтобы разложить любое такое произведение требуется 146 миллионов делений.
На этом примере сравним квадратичный алгоритм и линейный. Сравнение на пальцах, но представление даёт. Самый дорогой НОД для наших чисел стоит 92 деления. Ещё два деления чтобы сократить общий множитель. Общее число делений для двух массивов из n чисел есть 94 n2.
Линейный алгоритм потратит 146·106·2n. 2n чисел, каждое надо разложить.
Приравняем их чтобы узнать при каком n линейный алгоритм начнёт обгонять квадратичный по числу делений (я уже говорил - оценка грубая). В районе трёх миллионов:
94·n2 = 146·106·2·n
n ≈ 3.1·106
Тот случай, когда константу игнорировать нельзя. Я не вижу способа улучшить поведение линейного алгоритма в вышеприведённом "плохом случае". Отчасти это извиняет меня: я обещал поместить сюда ответ с линейным алгоритмом, но не буду. Но есть
Надежда
Есть квадратичный алгоритм, не дождётесь ответа на длинных массивах. Есть линейный алгоритм, совершенно непрактичный (на специальных примерах, но всё же). Как можно решать задачу?
Если есть длинная арифметика с произведением за n·log n (n - количество цифр в множителях), то за n·log2n можно вычислить произведение n чисел фиксированной разрядности. Полученные произведения сравниваются как они есть. Требуемую арифметику на коленке не напишешь, но она есть в библиотеках доступных на всех популярных языках программирования.
Ещё один способ опирается на китайскую теорему об остатках. Берёте простое число и вычисляете произведения чисел в массивах по его модулю (несложно считается за линейное время). Если для двух массивов произведения по модулю различны, значит и обычные произведения различны. Если одинаковы, надо взять другой модуль. Повторять до тех пор пока произведение модулей не превысит любое возможное произведение чисел в массивах. Например 2n больших модулей достаточно для массива длины n.
Это точный алгоритм, но опять таки квадратичный: каждый модуль проверяется за линейное время (за O(n)). Но и самих модулей тоже O(n).
Не всё так плохо. Выберем большой случайный простой модуль p1, вычислим произведения по нему для двух массивов. Если они оба равны нулю, в массивах есть множители кратные модулю. Сократим их (с проверкой степени) и пересчитаем произведения. Какова вероятность что произведения по модулю равны, а нормальные произведения - нет? Она обратно пропорциональна p1. Если такой вероятности недостаточно, выберете другой случайный простой модуль p2 (≠ p1). Если массивы прошли и этот тест, вероятность ошибки обратно пропорциональна p1p2. Повторяйте столько раз сколько вам нужно чтобы иметь практическую уверенность, что массивы действительно равны.
Последний алгоритм можно написать на коленке за пару вечеров. Нужен генератор больших случайных простых - это не сложно. Грубо говоря, генерируются большие случайные числа и проверяются на простоту вероятностным тестом (!).
Итого: есть детерминированный крайне сложный алгоритм за n·log2n и не очень сложный вероятностный алгоритм за n.