Bể nước

Points: 2

Time limit: 1.0s

Memory limit: 98M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, ~~kotlin~~, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Hôm nay Tico đi học được bạn cùng lớp đố một bài toán nhưng Tico vẫn chưa giải được. Các bạn hãy giúp Tico giả bài toán này nhé.

Có 2 bể nước, bể 1 có a lít nước và bể 2 có b lít nước: Ở mỗi lượt có thể chọn 1 trong 2 bể nước để thực hiện các phép toán sau

-Nếu số lượng nước trong bể đó chia hết cho 2, thì đổ 1/2 lượng nước trong bể đó ra ngoài

-Nếu số lượng nước trong bể đó chia hết cho 3, thì đổ 2/3 lượng nước trong bể đó ra ngoài

-Nếu số lượng nước trong bể đó chia hết cho 5, thì đổ 4/5 lượng nước trong bể đó ra ngoài

Hãy tính số lượt ít nhất để 2 bể nước bằng nhau

Input

2 số nguyên a,b \((1≤a,b≤10^9)\) - lượng nước của 2 bể nước

Output

Hãy in ra số lượt tối thiểu nếu không có cách nào thoả mãn thì in ra −1.

Ví dụ

Input1

3 6

Output1

Input2

2 8

Output2

Comments

TICHPX commented on Oct. 24, 2021, 7:09 a.m.

Code tham khảo

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,a2=0,a3=0,a5=0,b2=0,b3=0,b5=0;
    cin>>a>>b;
    c=__gcd(a,b);
    a/=c;
    b/=c;
    while(a%2==0) {a/=2;a2++;}
    while(a%3==0) {a/=3;a3++;}
    while(a%5==0) {a/=5;a5++;}
    while(b%2==0) {b/=2;b2++;}
    while(b%3==0) {b/=3;b3++;}
    while(b%5==0) {b/=5;b5++;}
    if(a!=1 || b!=1) cout<<-1;
    else cout<<max(a2,b2)-min(a2,b2)+max(a3,b3)-min(a3,b3)+max(a5,b5)-min(a5,b5);

}