Решение задачи "Дели! " с Codeforces

Без пояснения   Просмотров: 12


Вам задано целое число n.

Вы можете выполнять любую из следующих операций над ним любое (возможно, нулевое) количество раз:

Заменить n на n2, если n делится на 2;
Заменить n на 2n3, если n делится на 3;
Заменить n на 4n5, если n делится на 5.
Например, Вы можете заменить 30 на 15 при помощи первой операции, на 20 при помощи второй операции или на 24 при помощи третьей операции.

Ваша задача — найти минимальное количество операций, необходимое для того, чтобы получить 1 из n, или сказать, что это невозможно сделать.

Вам необходимо ответить на q независимых запросов.


Код

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
    int t; 
    cin >> t; 
    while (t--){
        int64 n, ans{}; 
        cin >> n;
        while (n % 2 == 0){
            n /= 2; 
            ans += 1;
        }
        while (n % 3 == 0){
            n /= 3; 
            ans += 2;
        }
        while (n % 5 == 0){
            n /= 5; 
            ans += 3;
        }  
        cout << ((n == 1) ? ans : -1) << '\n';
  }
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться