# 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.

10

4

## Sample Input 2

1000000000000000000

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;
}