Arcane Numbers 1
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
Vance and Shackler like playing games. One day, they are playing a game called "arcane numbers". The game is pretty simple, Vance writes down a finite decimal under base A, and then Shackler translates it under base B. If Shackler can translate it into a finite decimal, he wins, else it will be Vance’s win. Now given A and B, please help Vance to determine whether he will win or not. Note that they are playing this game using a mystery language so that A and B may be up to 10^12.
Input
The first line contains a single integer T, the number of test cases.
For each case, there’s a single line contains A and B.
For each case, there’s a single line contains A and B.
Output
For each case, output “NO” if Vance will win the game. Otherwise, print “YES”. See Sample Output for more details.
Sample Input
3
5 5
2 3
1000 2000
5 5
2 3
1000 2000
Sample Output
Case #1: YES
Case #2: NO
Case #3: YES
Case #2: NO
Case #3: YES
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; long long gcd(long long a,long long b)
{
if(a<b)
return gcd(b,a);
else if(b==)
return a;
else
return gcd(b,a%b);
} int main()
{
int T,ca=;
long long A,B;
int i,j,k,flg;
scanf("%d",&T);
while(T--)
{
scanf("%I64d %I64d",&A,&B);
long long C=gcd(A,B),D;
A=A/C,B=B/C;
flg=;
if(B>)
{
while()
{
if(B==)
break;
D=gcd(B,C);
if(D==)
{
flg=;
break;
}
B=B/D;
}
}
if(A>)
{
while()
{
if(A==)
break;
D=gcd(A,C);
if(D==)
{
flg=;
break;
}
A=A/D;
}
}
if(flg==)
printf("Case #%d: YES\n",ca);
else
printf("Case #%d: NO\n",ca);
ca++;
}
return ;
}