Матч 303, Простые палиндромы (PrimePalindromic)

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

Число называется палиндромом, если оно читается одинаково как слева направо, так и справа налево. Целое число называется простым палиндромным, если в результате конкатенации его простых множителей можно получить палиндром. Каждый простой множитель должен входить в палиндром столько раз, сколько он встречается в разложении самого числа. Если n = , то каждый простой множитель p_i должен входить в палиндром a_i раз.

Число 48 является простым палиндромным, так оно имеет простые множители 2, 2, 2, 2, 3 (48 = 2 * 2 * 2 * 2 * 3) и из них можно составить палиндром 22322. Число 2261 также является простым палиндромным, так как из его множителей 7, 17 и 19 можно составить палиндром 71917. Число 33 не является простым палиндромным.

Класс: PrimePalindromic

Метод: int count(int a, int b)

Ограничения: 2 £ a £ 10000, a £ b £ 10000.

Вход. Два целых числа a и b.

Выход. Количество простых палиндромных чисел, лежащих между a и b включительно.

Пример входа

a	b
2260	2262
2	9
2	100

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

1

7

36

РЕШЕНИЕ

перебор

Задача решается прямым перебором всех чисел от a до b, проверяя, является ли каждое из них простым палиндромным. Чтобы проверить, является ли число простым палиндромным, следует найти все множество его простых множителей и перебрать конкатенацию всех их возможных перестановок.

Функция factor(int n) раскладывает на простые множители число n и заносит найденные множители с учетом кратности в вектор v.

Функция IsPalindrom(string s) проверяет, является ли строка s палиндромом.

Функция IsPalindromic(int n) проверяет, является ли число n простым палиндромным. Процесс факторизации в функции factor реализован так, что массив v содержит все множители с учетом кратности в неубывающем порядке. То есть массив v после вызова функции факторизации будет содержать наименьшую перестановку. И в цикле do { … } while (…) будут перебраны все возможные перестановки.

ПРОГРАММА

#include <cstdio>

#include <cmath>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

vector<int> v;

void factor(int n)

{

v.clear();

for(int i = 2; i * i <= n; i++)

while(n % i == 0) v.push_back(i), n /= i;

if (n > 1) v.push_back(n);

}

int IsPalindrom(string s)

{

for(int i = 0; 2 * i <= s.size(); i++)

if (s[i] != s[s.size() - 1 - i]) return 0;

return 1;

}

int IsPalindromic(int n)

{

factor(n);

int i, flag = 0,len = v.size();

string s;

char s_temp[11];

do{

for(s = "", i = 0; i < len; i++)

sprintf(s_temp,"%d",v[i]),s += (string)s_temp;

if (IsPalindrom(s)) {flag = 1; break;}

} while(next_permutation(v.begin(),v.end()));

return flag;

}

class PrimePalindromic

{

public:

int count(int a, int b)

{

int i, count = 0;

for(i = a; i <= b; i++)

if (IsPalindromic(i)) count++;

return count;

}

};