Codeforces Round#218(Div.2)/371 B Fox Dividing Cheese(考え方問題)

http://codeforces.com/contest/371/problem/B
神題には必ず神解がある--そうすることを考えることができますか.
まず,2/3/5で完全に除去できないまで,1つの数を盲目的に除算した.
別の数を再利用して「ロールバック」を行います.△この語は、プログラムの更新/インストールにエラーが発生し、前回の正しい状態を返す動作のイメージ記述から来ています.
コードは次のとおりです.

/*15ms,0KB*/

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a, b, ans = 0;
	cin >> a >> b;
	for (int n = 2; n <= 5; n++) ///    4
	{
		int cnt = 0;
		while (a % n == 0) a /= n, ++cnt;
		while (b % n == 0) b /= n, --cnt; ///         
		ans += abs(cnt); /// abs      a,b 2,3,5             
	}
	cout << (a == b ? ans : -1);
	return 0;
}

【拡張1】
このアルゴリズムの複雑さはO(log ab)であり,2,3,5,7,11を選択しても...10000個の素数でもすぐに計算できます.
【拡張2】
除数が2,3,4,5なら?
まず判断する.
【拡張3】
除数が2,3,4,5,6なら...どうですか.
私はしばらくBFSのアルゴリズムしか考えられません.の
【拡張4】
最初にm個の違うものがあったら?
やはりBFSです..枝を切ってもいいかもしれません