1306: 狐狸分肉--最大公约数

Time Limit: 3 SecMemory Limit: 128 MB

Submit: 108Solved: 44

[Submit][Status][Web Board]

Description

从前有两只贪婪的小熊，有一天他们发现两块质量分别为A和B的肉。小熊是如此的贪婪所以他们都想要大的那块肉。就在这个时候一只狐狸经过并告

诉小熊我可以帮你们平分这两块肉。如果一块肉的质量是2的倍数，那么狐狸可以一次吃掉一半的肉。如果一块肉的质量是3的倍数，那么狐狸一次可

以吃掉三分之二。如果一块肉的质量是5的倍数，那么狐狸一次可以吃掉五分之四。小熊想了想后同意了狐狸的办法，但是他们有个条件就是狐狸必须用最少的次数使得两块肉的质量相等。你能告诉狐狸他最少可以吃几次才能使两块肉的质量相等吗？

Input

多组测试数据，每组测试数据包含两个正整数a,b（1<=a,b<=10^9）。

Output

对于每组测试数据，若狐狸不能使两块肉质量相等则输出-1，否则输出最少的次数。

Sample Input

15 20

14 8

6 6

Sample Output

3

-1

0

---

参考：ZCMU-1306-狐狸分肉 - ZCMUCZX的博客 - CSDN博客；求a和b的最大公约数 gcd(a, b) = gcd(b, a%b) - qq_42157089的博客 - CSDN博客这道题它说要使最后的两块肉质量一样，而且它又说狐狸可以把它只剩下三分之一或者二分之一或者五分之一，其实最后剩余两块肉的质量如果是一样的，那肯定和公约数有关系了。我们就可以算它们的最大公约数，我们这么想嘛，如果是15和30最大公约数是15，分别除下15得到的1和2，那么最终肯定能得到，因为2除2就为1了，再举个例子18,8它们的最大公约数是2，分别除下2得到了9和4我们能不能把这9和4除2，除3，除5，能不能相等，最后得到的两个数如果相等那就说明是可以分的，n经过相除之后肯定不是2,3,5的倍数了，m经过相除也是，所以如果在中间能让它们两个数相等的话，其实最后得出来的也是一样的

gcd(a,b)!!!!!

---

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

int gcd(int a,int b){

return b==0?a:gcd(b,a%b);

}

int main(){

int a,b,flag;

int sum;

while(~scanf("%d%d",&a,&b))

{

flag=0;

sum=gcd(a,b);

a/=sum;

b/=sum;

while(a%2==0){

a/=2;

flag++;

}

while(a%3==0){

a/=3;

flag++;

}

while(a%5==0){

a/=5;

flag++;

}

while(b%2==0){

b/=2;

flag++;

}

while(b%3==0){

b/=3;

flag++;

}

while(b%5==0){

b/=5;

flag++;

}

if(a==b)

printf("%d\n",flag);

else

printf("-1\n");

}

return 0;

}