首页 > 其他 > 详细

HDU5505

时间:2016-08-18 19:36:39      阅读:173      评论:0      收藏:0      [点我收藏+]

GT and numbers

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

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
 
 1 //2016.8.17
 2 #include<iostream>
 3 #include<cstdio>
 4 #define ll unsigned long long
 5 using namespace std;
 6 
 7 ll gcd(ll a, ll b)
 8 {
 9     return b==0?a:gcd(b, a%b);
10 }
11 
12 int main()
13 {
14     int T, cnt;
15     bool fg;
16     ll n, m;
17     cin>>T;
18     while(T--)
19     {
20         scanf("%I64d%I64d", &n, &m);
21         if(n==m){
22             puts("0");
23             continue;
24         }
25         if(n==0||m<n||m%n!=0)
26         {
27             puts("-1");
28             continue;
29         }
30         fg = true; cnt = 0;
31         while(m != n)
32         {
33             ll tmp = gcd(n, m/n);
34             if(tmp == 1){
35                 fg = false;
36                 break;
37             }
38             n *= tmp;
39             cnt++;
40         }
41         if(fg)
42             printf("%d\n", cnt);
43         else 
44               printf("-1\n");
45     }
46 
47     return 0;
48 }

 

HDU5505

原文:http://www.cnblogs.com/Penn000/p/5785041.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!