HDOJ 5505-GT and numbers

ゝ一世哀愁。 2022-08-20 05:16 28阅读 0赞

# GT and numbers #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1625 Accepted Submission(s): 409

Problem Description

You are given two numbers  N![Image 1][] and  M![Image 1][].  
  
Every step you can get a new  N![Image 1][] in the way that multiply  N![Image 1][] by a factor of  N![Image 1][].  
  
Work out how many steps can  N![Image 1][] be equal to  M![Image 1][] at least.  
  
If N can't be to M forever,print  −1![Image 1][].

Input

In the first line there is a number  T![Image 1][].  T![Image 1][] is the test number.  
  
In the next  T![Image 1][] lines there are two numbers  N![Image 1][] and  M![Image 1][].  
  
 T≤1000![Image 1][],  1≤N≤1000000![Image 1][],  1≤M≤2![Image 1][]63![Image 1][]![Image 1][].  
  
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

[BestCoder Round \#60 ][BestCoder Round _60]

解题思路：

辗转相除法，注意定义不要溢出就行了。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    unsigned long long i,j,k,l,m,n,help;
    int gcd(unsigned long long m,unsigned long long n)
    {//求最大公约数 
    	help=1;
    	while(help!=0)
    	{
    		help=m%n;
    		m=n;
    		n=help;
    	}
    	return m;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int flag=0;
    		scanf("%I64d%I64d",&n,&m);
    		if(m<n||m%n||n==0)
    		{
    			printf("-1\n");
    			continue; 
    		}
    		if(n==m)
    		{
    			printf("0\n");
    			continue;
    		}
    		int ans=0;
    		while(n!=m)
    		{
    			if(gcd(m/n,n)==1)
    			{
    				flag=1;
    				break;
    			}
    			n=n*(gcd(m/n,n));
    			ans++;
    		}
    		if(flag==0)
    		printf("%d\n",ans);
    		else
    		printf("-1\n");
    	}
    	return 0;
    }

[Image 1]: 
[BestCoder Round _60]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2360&source=1&searchmode=source