CF371B Fox Dividing Cheese
Aya_tt
·
·
题解
1，求出输入 a,b 的 \gcd，即最大公约数，就像样例中 \gcd(15,20)=5。
int gcd(int a,int b){
if(b == 0) {
return a;
}
return gcd(b,a % b);
}
这是最大公约数的函数，用的方法是辗转相除法。
可是为什么要求最大公约数呢？题面上：假如这块蛋糕的重量是 2 的倍数，那么狐狸可以吃掉二分之一；假如蛋糕的重量是 3 的倍数，那么狐狸可以吃掉三分之二；假如蛋糕的重量是 5 的倍数，狐狸可以吃掉五分之四。
翻译过来就是：
如果是 2 的倍数，就除以 2。
如果是 3 的倍数，就除以 3。
如果是 5 的倍数，就除以 5。
所以蛋糕的数量就会不停除除除除除......直到最后他们一样，这是第一步。
2,如上，不停作除法，可是除的数有限制，只能除 2，除 3，除 5，所以我们不妨设 \gcd(a,b)=k,a\leftarrow a\div k,b\leftarrow b\div k 就是除的数，因为只能除 2、3、5，所以他除以 2、3、5 一定能得到 1，不然就分不了，输出 -1。
代码如下：
while(a % 2 == 0) a /= 2;
while(a % 3 == 0) a /= 3;
while(a % 5 == 0) a /= 5;
if(a != 1){ //如果是倍数，除完肯定是 1。
cout<<-1;
return 0;
}
这样第二步就做完了。
------------
第三步就是要统计狐狸吃的最小次数了。
首先要建立一个统计的变量 $cnt$ 。
如何统计呢？
把他放到 `while` 循环里面不就完了吗，除一次， $cnt$ 就加一，这不就结了吗？
------------
接下来上最终代码
```c++
#include<bits/stdc++.h>
using namespace std;
int cnt,a,b;
int gcd(int a,int b){
if(b == 0) {
return a;
}
return gcd(b,a % b);
}
int main(){
cin>>a>>b;
int k = gcd(a,b);//最最大公约数
a /= k,b /= k;//求除的数
while(a % 2 == 0) cnt++,a /= 2;
while(a % 3 == 0) cnt++,a /= 3;
while(a % 5 == 0) cnt++,a /= 5;
while(b % 2 == 0) cnt++,b /= 2;
while(b % 3 == 0) cnt++,b /= 3;
while(b % 5 == 0) cnt++,b /= 5; //以上都是在统计cnt，在判断是否都是2,3,5的倍数。
if(a != 1 || b != 1) {
cout<<-1;
return 0;
}
cout<<cnt;//输出
}
```