Матч 302, Увеличение делителя (DivisorInc)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 1

Имеется целое число k. К нему можно прибавить любой его делитель, отличный от 1 и k. К полученному числу снова применяется описанная операция. По заданным двум числам n и m необходимо найти минимальное количество таких операций, в результате которых можно получить из числа n число m.

Класс: DivisorInc

Метод: int countOperations(int N, int M)

Ограничения: 4 £ n £ 10⁵, n £ m £ 10⁵.

Вход. Два числа n и m.

Выход. Наименьшее количество описанных операций, необходимое для преобразования числа n в m. Если из n нельзя получить m, то вывести -1.

Пример входа

n	m
4	24
4	576
8748	83462

Пример выхода

5

14

10

РЕШЕНИЕ

поиск в ширину

Введем целочисленный массив used, в котором used[i] содержит наименьшее количество ходов, за которое из числа n можно получить i. Если used[i] = ¥, то получить i из n невозвожно (или значение еще не посчитано). Изначально положим used[n] = 0. Двигаемся по i от n до m – 1 и для каждого i, для которого used[i] ¹ ¥, находим его делители. Если j – делитель числа i (j £), то i/j также будет делителем i. Для каждого найденого делителя j числа i пересчитываем значение used[i + j]. Если used[i] + 1 < used[i + j], то положим used[i + j] = used[i] + 1. По окончании цикла по i результат находится в ячейке used[m], если оно не равно ¥. Ииначе возвращаем -1.

Отдельно следует обработать случай, когда n = m. Возвращаемое значение в таком случае равно 0.

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

int used[200002];

class DivisorInc

{

public:

int countOperations(int n, int m)

{

int i, j;

if (n == m) return 0;

memset(used,0x7F,sizeof(used));

used[n] = 0;

for(i = n; i < m; i++)

{

if (used[i] == 0x7F7F7F7F) continue;

for(j = 2; j * j <= i; j++)

if (i % j == 0)

{

if (used[i] + 1 < used[i + j]) used[i + j] = used[i] + 1;

if (used[i] + 1 < used[i + (i/j)]) used[i + (i/j)] = used[i] + 1;

}

}

return (used[m] == 0x7F7F7F7F) ? -1 : used[m];

}

};

Реализация программы при помощи очереди.

#include <cstdio>

#include <deque>

using namespace std;

deque<pair<int,int> > d;

int i, flag = 0, used[100001];

class DivisorInc

{

public:

int countOperations(int n, int m)

{

pair<int,int> p;

if (n == m) return 0;

memset(used,0,sizeof(used));

d.push_back(make_pair(n,0));used[n] = 1;

while(!d.empty())

{

p = d[0]; d.pop_front();

if (p.first == m) {flag = 1; break;}

for(i = 2; i * i <= p.first; i++)

if (p.first % i == 0)

{

if((p.first+i <= m) && !used[p.first+i])

{

used[p.first + i] = 1;

d.push_back(make_pair(p.first + i, p.second + 1));

}

if((p.first + p.first/i <= m) && !used[p.first + p.first/i])

{

used[p.first + p.first/i] = 1;

d.push_back(make_pair(p.first + p.first/i, p.second + 1));

}

}

}

return flag ? p.second : -1;

}

};