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