题解 CF371B 【Fox Dividing Cheese】
ShineEternal
2019-09-21 20:31:06
[更佳阅读](https://blog.csdn.net/kkkksc03/article/details/101117693)
## Description：
## Solution：
$idea1:$
直接bfs搜索，因为一个数的约数个数还真不多。
但是有些麻烦？
$idea2:$
然后在分别试除$2,3,5$这几个数的时候也有点技巧，可以看一下
```cpp
#include<cstdio>
using namespace std;
int gcd(int x,int y)
{
if(y==0)return x;
return gcd(y,x%y);
}
int main()
{
int a,b,c;
scanf("%d%d",&a,&b);
c=gcd(a,b);
a=a/c;
int cnt=0;
b=b/c;
for(int i=2;i<=5;i+=(i-1))
{
while(a%i==0)
{
cnt++;
a=a/i;
}
while(b%i==0)
{
cnt++;
b=b/i;
}
}
if(a!=b)printf("-1\n");
else printf("%d\n",cnt);
return 0;
}
```