hdu 5505 GT and numbers【BestCoder Round #60】

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## hdu 5505 GT and numbers【BestCoder Round #60】

angel_imp 2015-10-24 15:52:00 浏览804

# GT and numbers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1066    Accepted Submission(s): 285

Problem Description
You are given two numbers N and M.

Every step you can get a new N in the way that multiply N by a factor of N.

Work out how many steps can N be equal to M at least.

If N can't be to M forever,print 1.

Input
In the first line there is a number T.T is the test number.

In the next T lines there are two numbers N and M.

T10001N1000000,1M263.

Be careful to the range of M.

You'd better print the enter in the last line when you hack others.

You'd better not print space in the last of each line when you hack others.

Output
For each test case,output an answer.

Sample Input

3 1 1 1 2 2 4

Sample Output

0 -1 1

Source

给出两个数N和M。
N每次可以乘上一个自己的因数变成新的N。

第一行读入一个数T表示数据组数。

T\leq1000, 1\leq N \leq 1000000,1 \leq M \leq 2^{63}.

对于每组数据，输出一个数表示答案。

B存在A没有的质因数也显然无解。

B可以刚好等于2^{63}，这样就要开unsigned long long。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e4+5;
const int mod = 1000000007;
const double eps = 1e-7;

ULL gcd(ULL a, ULL b)
{
if(b == 0)
return a;
return gcd(b, a%b);
}
int main()
{
int T;
ULL m, n;
cin>>T;
while(T--)
{
cin>>n>>m;
if(m%n != 0)
{
puts("-1");
continue;
}
ULL ret = 0;
bool ok = 0;
ULL kk =gcd(m, n);
while(m != n)
{
if(m%n != 0 || kk == 1)
{
ok = 1;
break;
}
ret++;
kk = gcd(n, m/n);
n *= kk;
}
if(ok)
puts("-1");
else
cout<<ret<<endl;
}
return 0;
}

angel_imp
+ 关注