Codeforces 371B.Fox Dividing Cheese

204

题目



Description  


Two little greedy bears have found two pieces of cheese in the forest of weight a and b grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that ", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal".

The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.



Input  


The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 109).


Output  


If the fox is lying to the little bears and it is impossible to make the pieces equal, print -1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.


Sample Input  



Input  


15 20


Output  


3


Input  


14 8


Output  


-1


Input  


6 6


Output  


0


题解



ab 的最大公因数
输出最少需要除以 2 3 5 多少次,能使 ab 都变成最大公因数
如果 a==b 输出 0
如果不能得到,输出 -1

读懂题意后直接模拟即可
~~然而题意真难读懂~~

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
#include <iomanip>
using namespace std;

const int d[] = {2,3,5};

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

bool Do() {
int a,b;
if(!(cin >> a >> b))
return false;

if(a == b) {
cout << 0 << endl;
return true;
}


int ans = 0;
int g = gcd(a,b);

a /= g;
b /= g;
for(int i = 0;i < 3;i++) {
while(a%d[i] == 0) {
a /= d[i];
ans++;
}
while(b%d[i] == 0) {
b /= d[i];
ans++;
}
}
if(a == 1 && b == 1)
cout << ans << endl;
else
cout << -1 << endl;
return true;
}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);

while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论