Реализация факторизованного представления структурой

Настало время обзавестись в нашем инструментарии реализацией факторизованного представления чисел. Воспользуемся представлением в виде структуры.

Сами числа будут описаны в форме

#include <iostream>

#include <vector>

using namespace std;

 

struct factorized{              //структура факторизации

vector<int>p, q;            // множители и степени

factorized(){};             // конструктор по умолчанию

factorized(longlong);       // конструктор по длинному целому

factorized& operator =(const factorized&); //присваивание

const factorized operator *(const factorized&); //умножение

friend ostream& operator <<(ostream&, const factorized&); //вывод

longlongvalue();      // значениечисла

};

 

// конструктор по длинному целому - реализация

factorized::factorized(longlongx){

for(intd = 2, xx = x; x>1 &&d*d<= xx; d++){ // xx – староезн. x

if(x % d == 0) {          // поиск простых множителей

p.push_back(d); // производим от 2 до sqrt(x)

q.push_back(0);

   }

while(x % d == 0){        // считаем степени для

x /= d;              // множителей в разложении

q[q.size()-1]++;

   }

}

if(x>1) {                 // если остался ещё простой

p.push_back(x);      // множитель больше sqrt(xx)

q.push_back(1);

}

}

 

// потоковыйвывод - реализация

ostream& operator <<(ostream& os, const factorized& x){

if(x.p.empty()) os << 1;

else

for(int i = 0; i < x.p.size(); i++){ // выводим в виде

   os << x.p[i] << '^' << x.q[i]; // 2^3*3^1*5^2 (для600)

   if(i < x.p.size()-1) os << '*';

}

return os;

}

 

//присваивание - реализация

factorized& factorized::operator =(const factorized& op){

this->p = op.p;

this->q = op.q;

return *this;

}

 

// произведение факторизованных чисел - реализация

const factorized factorized::operator *(const factorized& op){

factorized res;

  long long i = 0, j = 0;

 bool ii, jj;                          // ii==true если берем

while(i<p.size() || j<op.p.size()){ // множитель от первого

   ii = jj = false;             // числа, jj– от второго

   if(i == p.size()) {ii = false; jj = true;}

   else if(j==op.p.size()) {ii = true; jj = false;}

           else {ii = p[i] <= op.p[j]; jj = op.p[j] <= p[i];}

   res.p.push_back(ii ? p[i] : op.p[j]);

   res.q.push_back(ii*q[i] + jj*op.q[j]);

   i += ii; j += jj;

}

return res;

}

 

// определить значение факторизованного числа - реализация

long long factorized::value(){

long long res = 1;

for(int i = 0; i < p.size(); i++)

   for(int j = 0; j < q[i]; j++)

       res *= p[i];

return res;

}

Следует отметить, что множители в такой модели выстраиваются в порядке возрастания и при произведении чисел в факторизованной модели, возрастающий порядок сохраняется.

Задача №222.  Степень (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Источник задачи: Московская олимпиада по информатике 2003/2003 г.

Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу – для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году меняется только число A.

Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.

Входные данные

Единственное число A (1 ≤ A ≤ 10⁹ – на всякий случай, вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).

Выходные данные

Единственное число N.

Примеры

№	Ввод	Вывод
1	8	4
2	13	13

Решение

Воспользуемся факторизованной моделью представления чисел. Если A представить в виде:

Где все множители – простые числа, то, очевидно, минимальное возможное значение Nравно:

Также, очевидно, N≤A, поскольку число A^Aбудет делиться на Aбез остатка. Соответственно, число Nкратно N_minи не превышает A.

Возводить числа, представленные в факторизованной модели в любую степень, в том числе равную самому числу очень легко. Например, если

то

Далее можно воспользоваться описанной ранее структуройfactorized, из которой, впрочем, нам потребуются лишь конструктор по длинному целому и оператор присваивания.

struct factorized{

...

};

int main(){

int a, n = 1, i, j, m;

cin >> a;

factorizedb(a), c;          // b – этофакторизованноеa

for(i = 0; i < b.p.size(); i++)

   n *= b.p[i];            // находим n_min

for(m = n; n <= a; n += m){ // перебираем n от n_min до a

   c = n;                  // с – это факторизованное n

   for(i = j = 0; i<b.p.size(); i++){

       while(b.p[i] > c.p[j]) j++;

       if(b.q[i] > c.q[j]*n) break;

   }

   if(i==b.p.size()) {cout << n; return 0;}

}

}

Рекурсия

Итерация свойственна человеку, рекурсия божественна.

Л. Петер Дойч