[CF 371B]Fox Dividing Cheese

danihao123 posted @ 2016年8月16日 13:57 in 题解 with tags codeforces 数论 数学 , 273 阅读
转载请注明出处:http://danihao123.is-programmer.com/

狐狸的三种操作的实质是除二,除三,除五。由此我们可以猜想在最优策略下,两块蛋糕最后的重量应该是[tex]gcd(a,b)[/tex]。然后试除即可。

(大胆猜想,不用证明

代码:

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
	if(!b)
		return a;
	else
		return gcd(b,a%b);
}
static int P[3]={2,3,5};
inline int min_fj(int source,int direction){
	register int i,ans=0;
	source/=direction;
	if(source==1)
		return 0;
	for(i=2;i>=0;i--){
		while(source%P[i]==0){
			source/=P[i];
			ans++;
		}
	}
	if(source==1)
		return ans;
	else
		return -1;
}
int main(){
	register int direction,t1,t2;
	int a,b;
	cin>>a>>b;
	if(a==b){
		cout<<0<<endl;
		return 0;
	}
	direction=gcd(a,b);
	t1=min_fj(a,direction);
	if(t1==-1){
		cout<<-1<<endl;
		return 0;
	}
	t2=min_fj(b,direction);
	if(t2==-1){
		cout<<-1<<endl;
		return 0;
	}
	cout<<t1+t2<<endl;
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter