题目链接 : http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=641&pid=1002
思路 :
N有若干个质因子, N = a^b * c^d * e^f......
M也有若干个质因子, M = a^(b+k) * c(d+k1) * e^(f+k2)......
N能到达M的条件是它们的质因子必须完全相同
N每次可以乘上它的若干个质因子, 直到这个质因子的幂次等于M这个质因子的幂次
考虑这样一个事实, N乘上某个质因子的a次幂后, 新的N可以乘上该质因子的2a次幂
故对于每个质因子, N的次数每次平方, cnt++, 直到大于等于M这个质因子的次数, 取最大的cnt即可
要注意的是M的范围会爆long long 所以要开unsigned long long
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; typedef unsigned long long LL; const int MAXN = 1e6+;
const int PRI_NUM = 2e6+; bool vis[PRI_NUM];
int prime[MAXN];
int factor_n[MAXN];
int factor_m[MAXN];
int prime_n[];
int prime_m[]; void Pre()
{
for(int i = ; i <= PRI_NUM; i++) {
if(vis[i] == ) {
for(int j = i+i; j <= PRI_NUM; j+=i) {
vis[j] = ;
}
}
}
int cnt = ;
for(int i = ; i <= PRI_NUM; i++) {
if(vis[i] == ) {
prime[cnt++] = i;
}
}
} void Init()
{
memset(prime_n, , sizeof(prime_n));
memset(prime_m, , sizeof(prime_m));
} int main()
{
Pre(); int t;
int n;
LL m; scanf("%d", &t);
while(t--) {
Init();
scanf("%d %I64u", &n, &m);
if(m == n) {
printf("0\n");
continue;
}
if(m % n || n <= ) {
printf("-1\n");
continue;
}
int cnt = ;
for(int i = ; i < MAXN; i++) {
if(n == ) break;
if(n % prime[i] == ) {
factor_n[cnt] = prime[i];
while(n % prime[i] == ) {
n /= prime[i];
prime_n[cnt]++;
}
cnt++;
}
}
if(n > ) {
factor_n[cnt] = n;
prime_n[cnt] = ;
cnt++;
}
for(int i = ; i < cnt; i++) {
while(m % factor_n[i] == ) {
m /= factor_n[i];
prime_m[i]++;
}
}
if(m > ) {
printf("-1\n");
continue;
}
int ans = ;
for(int i = ; i < cnt; i++) {
int k = ;
while(prime_n[i] < prime_m[i]) {
prime_n[i] <<= ;
k++;
}
if(k > ans) ans = k;
}
printf("%d\n", ans);
} return ;
}
另外看到一种很强的做法
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; typedef unsigned long long ULL; ULL Gcd(ULL a, ULL b)
{
ULL r;
while(a % b) {
r = a % b;
a = b;
b = r;
}
return b;
} int main()
{
int t;
ULL n, m; scanf("%d", &t);
while(t--) {
scanf("%I64u %I64u", &n, &m);
int ans = ;
bool flag = ;
while(n != m) {
if(m % n) {
flag = ;
break;
}
ULL temp = Gcd(m / n, n);
if(temp == ) {
flag = ;
break;
}
n *= temp;
ans++;
}
if(flag == ) {
printf("%d\n", ans);
}
else printf("-1\n");
} return ;
}