# 14254: 【原4254】235

## 题目

### 题目描述

author: Guo Linsong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4254

## Description

You are given an integer \(n\).

You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:

Replace \(n\) with \(\frac{n}{2}\) if \(n\) is divisible by \(2\);

Replace n with \(\frac{2n}{3}\) if \(n\) is divisible by \(3\);

Replace n with \(\frac{4n}{5}\) if \(n\) is divisible by \(5\).

For example, you can replace \(30\) with \(15\) using the first operation, with \(20\) using the second operation or with \(24\) using the third operation.

Your task is to find the minimum number of moves required to obtain \(1\) from \(n\) or say that it is impossible to do it.

## Input Format

An integer number \(n(1 \leq n \leq 10^{18})\).

## Output Format

If it is impossible to obtain \(1\) from \(n\), print \(-1\).

Otherwise, print the minimum number of moves required to do it.

## Sample Input 1

10

## Sample Output 1

4

## Sample Input 2

1000000000000000000

## Sample Output 2

72

## ligongzzz's solution

```
#include <iostream>
using namespace std;
using ull = unsigned long long;
int main() {
ull n, a = 0, b = 0, c = 0;
cin >> n;
for (; n % 5ull == 0; n /= 5ull, ++c);
for (; n % 3ull == 0; n /= 3ull, ++b);
for (; n % 2ull == 0; n /= 2ull, ++a);
if (n != 1)
cout << -1;
else
cout << a + 2ull * b + 3ull * c;
return 0;
}
```