[Codeforces]Fox Dividing Cheese

[Codeforces]Fox Dividing Cheese

原题链接

狐狸和熊
听起来像寓言故事

就是先求出来a,b的最大公约数
然后看看吃几次能成最大公约数
感觉好像不太对
但是过了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<map>
#include<ctime>
#define MAX 1000000007
#define LL long long
using namespace std;int a,b,ac,bc,tot,c;int gcd(int x,int y)
{int r;if(y>x){r=x;x=y;y=r;}while(x%y){r=x%y;x=y;y=r;}   return y;
}int main()
{scanf("%d%d",&a,&b);if(a==b){printf("0");return 0;}c=gcd(a,b);ac=a/c;bc=b/c;if((ac%2)&&(ac%3)&&(ac%5)&&(ac!=1)){printf("-1");return 0;}if((bc%2)&&(bc%3)&&(bc%5)&&(bc!=1)){printf("-1");return 0;}   while(ac!=1){if(ac%2==0&&ac!=1){ac=ac/2;tot++;}if(ac%3==0&&ac!=1){ac=ac/3;tot++;}if(ac%5==0&&ac!=1){ac=ac/5;tot++;}   if((ac%2)&&(ac%3)&&(ac%5)&&(ac!=1)){printf("-1");return 0;}   }while(bc!=1){if(bc%2==0&&bc!=1){bc=bc/2;tot++;}if(bc%3==0&&bc!=1){bc=bc/3;tot++;}if(bc%5==0&&bc!=1){bc=bc/5;tot++;}   if((bc%2)&&(bc%3)&&(bc%5)&&(bc!=1)){printf("-1");return 0;}   }printf("%d",tot);return 0;
}

顺便还有一个bfs版

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<ctime>
#define LL long long
using namespace std;struct nico
{int a,b,tot;
};int bfs(int ap,int bp)
{queue<nico>q;nico k;k.a=ap;k.b==0;q.push(k);while(!q.empty()){k=q.front();q.pop();if(k.a==k.b) ;if(k.a>k.b){if(k.a%2==0){nico t;t.a=k.a/2;t.b=k.&#+1;q.push(t);}if(k.a%3==0){nico t;t.a=k.a/3;t.b=k.&#+1;q.push(t);}if(k.a%5==0){nico t;t.a=k.a/5;t.b=k.&#+1;q.push(t);}   }if(k.a<k.b){if(k.b%2==0){nico t;t.a=k.a;t.b=k.b/&#+1;q.push(t);}if(k.b%3==0){nico t;t.a=k.a;t.b=k.b/&#+1;q.push(t);}if(k.b%5==0){nico t;t.a=k.a;t.b=k.b/&#+1;q.push(t);}   }}return -1;
}int main()
{int a,b,ans;scanf("%d%d",&a,&b);if(a==b){printf("0");return 0;}ans=bfs(a,b);printf("%d",ans);return 0;
}