自己翻译
如果想不出正解的话可以直接搜索，BFS也能过，但写起来太麻烦
数论做法：
如果能达到要求的话，最后一定要吃成a,b的最大公约数
那就一口一口的吃，先吃1/2，再吃2/3，再吃4/5，如果最后吃不成一样的，就无法完成，如果可以，就输出所有动作的和，即
cout<<p2[0]+p2[1]+p3[0]+p3[1]+p5[0]+p5[1];
完整代码（bfs版）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct zhw{
int a;
int b;
int tot;
};
int cnt=123456789,flag;
void bfs(int a,int b)
{
queue <zhw> q;
zhw que;
que.a=a;
que.b=b;
que.tot=0;
q.push(que);
while(!q.empty())
{
que=q.front();
q.pop();
if(que.a==que.b)
{
cnt=que.tot;
flag=1;
}
if(que.a>que.b)
{
if(que.a%2==0)
{
zhw Tot;
T.a=que.a/2;
T.b=que.b;
T.tot=que.tot+1;
q.push(T);
}
if(que.a%3==0)
{
zhw Tot;
T.a=que.a/3;
T.b=que.b;
T.tot=que.tot+1;
q.push(T);
}
if(que.a%5==0)
{
zhw T;
T.a=que.a/5;
T.b=que.b;
T.tot=que.tot+1;
q.push(T);
}
}
if(que.a<que.b)
{
if(que.b%2==0)
{
zhw T;
T.a=que.a;
T.b=que.b/2;
T.tot=que.tot+1;
q.push(T);
}
if(que.b%3==0)
{
zhw T;
T.a=que.a;
T.b=que.b/3;
T.tot=que.tot+1;
q.push(T);
}
if(que.b%5==0)
{
zhw T;
T.a=que.a;
T.b=que.b/5;
T.tot=que.tot+1;
q.push(T);
}
}
}
}
int main()
{
int x,y;
cin>>x>>y;
bfs(x,y);
if(flag==0)
printf("-1");
else
printf("%d",cnt);
return 0;
}
数论版
#include <iostream> #include <cmath> using namespace std; int pw(int &a,int b) { int t=0; while(a%b==0) { a=a/b; t++; } return t; } int gcd(int m,int n) { if(n==0) return m; else return gcd(n,m%n); } int main() { int p2[2],p3[2],p5[2]; int a,b; int z; cin>>a>>b; z=gcd(a,b); a=a/z,b=b/z; p2[0]=pw(a,2); p2[1]=pw(b,2); p3[0]=pw(a,3); p3[1]=pw(b,3); p5[0]=pw(a,5); p5[1]=pw(b,5); if(a!=b) { cout<<"-1"; return 0; } else cout<<p2[0]+p2[1]+p3[0]+p3[1]+p5[0]+p5[1]; return 0; }