1

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

Условие задачи:
В этой задаче рассматриваются только чётные целые числа. Чётное натуральное число 𝑛 будем называть чётнопростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые. Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно.

Входные данные:
Дано чётное натуральное 𝑛 ≤ 109.

Выходные данные:
Если число 𝑛 — чётнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители. Сложность алгоритма должна быть О(√n).

Мой код:

def even_prime_check(n): # проверка числа на чётно-простоту
    if n%4 == 0:
        return False
    else:
        return True

def even_prime_factorization(n): # функция для не чётно-простого числа
    a = []
    b = []
    a.append(n//2)
    a.append(2)
    check1 = a[0]
    check2 = a[1]

    for d in range(6,10**6,4):
        if n%d == 0 and even_prime_check(n//d) and n//d != check2 and d != check1:
            b.append(n//d)
            b.append(d)
            break

    return a,b

n = int(input())
a,b = even_prime_factorization(n)

if even_prime_check(n):
    print('prime')

elif len(a) == 2 and len(b) == 0:
    print('single')
    print(' '.join(map(str, a)))

elif len(a) == 2 and len(b) == 2:
    print('many')
    print(' '.join(map(str, a)))
    print(' '.join(map(str, b)))

Я тестирую эту программу, вроде всё верно. Но моё решение засчитывается как неверное. Помогите, пожалуйста, найти ошибку и исправить код.

5
  • 4
    Проверка на четнопростоту - не делится на 4. Всё.
    – Harry
    8 июн 2020 в 16:45
  • @Harry, я изменил функцию проверки на чётнопростоту, но программа до сих пор не проходит проверку (19/28 тестов пройдено). Ещё непонятная ситуация, если ввести цифру 8: программа ничего не выводит. По сути, 8 — и не чётнопростое, и нет чётнопростых делителей (4 — не чётнопростое). Непонятно, как с этим справится. 8 июн 2020 в 17:15
  • Понимаете, я знаю, как решить, но не знаю, как это написать на Питоне :( Хотите, дам решение на С++?
    – Harry
    8 июн 2020 в 17:20
  • 1
    @Daniil Savinov 8 = 2 * 2 * 2 двух и более
    – MBo
    8 июн 2020 в 17:24
  • @Harry, Боюсь, не смогу перевести… Совсем его не знаю. Может, Вы можете написать решение на C++, описывая при помощи комментария каждую строчку? Тогда мне будет проще понять, что Вы делаете. Или можете просто текстом написать последовательность Ваших действий. Сделайте, как Вам удобно. Заранее спасибо! 8 июн 2020 в 17:24

2 ответа 2

4
int main()
{
    int n;
    cin >> n;
    if (n%4)                // Если не делится на 4 - выводим, что простое
    {
        cout << "prime\n";
        return 0;
    }
    int two = 0;            // Считаем степень 2 в разложении
    while(n%2 == 0)         // пока делится на 2 - 
    {
        two++;              // увеличиваем показатель
        n /= 2;             // само число делим на 2
    }
    vector<int> ps;         // Здесь массив нечетных простых делителей

    for(int d = 3; n > 1 && d*d <= n; d+=2)   // Для всех нечетных делителей от 3
    {                         // и до корня из n, с шагом 2
        while(n%d == 0)       // Пока делится (и если делится) на d
        {
            ps.push_back(d);  // вносим в массив
            n /= d;           // и делим на d
        }
    }
    if (n > 1) ps.push_back(n);  // Все что осталось простого - тоже в массив

    if (ps.size() <= 1)   // Если только один нечетный множитель - ответ 2 2 2... 2*d
    {                     // если его нет - просто двойки
        cout << "single\n";
        for(int i = 0; i < two-1; ++i) cout << "2 ";  // Выводим двойки
        cout << (ps.size()==0 ? 2 : 2*ps[0]) << endl; // Последний элемент - 2 или 2d, если есть
    }
    else
    {
        cout << "many\n";
        // Пусть в массиве простых нечетных делителей - d0 d1 d2...
        // Тогда первая выводимая строка - 2 2 .. 2 2*d0 2*d1*d2...

        for(int i = 0; i < two-2; ++i) cout << "2 ";
        cout << 2*ps[0] << " ";        // Это и есть 2*d0
        n = 1;  // Тут будет d1*d2...
        for(int i = 1; i < ps.size(); ++i) n *= ps[i];  // Перемножили
        cout << 2*n << endl;                            // Вывели 2*d1*d2...

        // Второй вывод - 2 2 .. 2 2 2*d0*d1*d2...
        for(int i = 0; i < two-1; ++i) cout << "2 ";    // Вывели двойки
        cout << 2*n*ps[0] << endl;                      // Вывели 2*d0*d1*d2...
    }
}

Все это благополучно проходит тестовую систему.. Весь код - https://ideone.com/otGj84

8
  • Как-то много кода, не?
    – Qwertiy
    8 июн 2020 в 17:59
  • @Qwertiy Так ведь писалось на коленке со скоростью набора :) - я не пытался сделать красиво или даже эффективно (можно было не разгребать все простые делители - достаточно одного было).
    – Harry
    8 июн 2020 в 18:06
  • А, тьфу, я накосячил. Надо на чётные раскладывать, а не на любые.
    – Qwertiy
    8 июн 2020 в 18:36
  • @Qwertiy, пожалуйста, помогите реализовать саму функцию. Мне не был понятен Ваш удалённый ответ. Я пытался реализовать хотя бы нахождение maxPowOf2ThatIsDivederOf(n), но не получилось. 8 июн 2020 в 18:50
  • 1
    @DaniilSavinov, удалённый ответ был неправильным. Сейчас правильный будет, минутку.
    – Qwertiy
    8 июн 2020 в 18:50
1

https://ideone.com/jlfdZu

def solve(n):
  d = 0
  while not (n&1):
    d += 1
    n //= 2

  a = [2]*d
  a[-1] *= n

  if d == 1:
    print("prime")
    return

  for x in range(3, int(n**.5)+1, 2):
    if not (n%x):
      b = a[:]
      b[-1] //= x
      b[-2] *= x
      print("many")
      print(" ".join(map(str, a)))
      print(" ".join(map(str, b)))
      return

  print("single")
  print(" ".join(map(str, a)))

from sys import stdin

for line in stdin:
  print("=== " + line.strip() + " ===")
  solve(int(line))
2
  • Спасибо Вам большое! Решение прошло проверку. Только Ваше решение мне немного непонятно. Мне хотелось бы в нём разобраться. Подскажите, пожалуйста, что Вы делаете на строках №3-8, №14-18 и №27-31? 8 июн 2020 в 19:41
  • 1
    27-31 - это чтение ввода пока он не закончится и обработка числа в каждой строке.
    – Qwertiy
    8 июн 2020 в 19:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.