题意:
给出a,b。问a和b经过最少几步的 /2 /3 /5变化可以相等。
看完官方题解才明白
官方题解 It is easy to see that the fox can do three type of operations: divide by 2, divide by 3 and divide by 5. Let’s write both given numbers in form a = x·2a2·3a3·5a5, b = y·2b2·3b3·5b5, where x and y are not dibisible by 2, 3 and 5. If x ≠ y the fox can’t make numbers equal and program should print -1. If x = y then soluion exists. The answer equals to |a2 - b2| + |a3 - b3| + |a5 - b5|, because |a2 - b2| is the minimal number of operations to have 2 in the same power in both numbers, |a3 - b3| is the minimal number of operations to have 3 in the same power in both numbers, and |a5 - b5| is the same for 5.整体思路:
如果a,b经过所有的 /2 /3 /5操作后,数值不等,那么一定无法通过变化得到。
反之,如果最后相等了,那必定有解。那么2 3 5 操作的差值就是解
代码while循环写多了。可以封装函数
#include<iostream> #include <math.h> using namespace std; int main() { int a,b; while(cin>>a>>b){ int a2=0,a3=0,a5=0; int b2=0,b3=0,b5=0; while(a%2==0) { a=a/2; a2++; } while(b%2==0) { b=b/2; b2++; } while(a%3==0) { a=a/3; a3++; } while(b%3==0) { b=b/3; b3++; } while(a%5==0) { a=a/5; a5++; } while(b%5==0) { b=b/5; b5++; } if(a!=b) cout<<-1<<endl; else cout<<fabs(a2-b2)+fabs(a3-b3)+fabs(a5-b5)<<endl; } return 0; }