2015
05-23

# Arcane Numbers 1

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.

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.

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.

3
5 5
2 3
1000 2000

Case #1: YES
Case #2: NO
Case #3: YES

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn = 1000005;
long long prime[maxn];
bool v[maxn];
int top = 0;
void init(){
memset(v,false,sizeof(v));
for(int i = 2;i < maxn;i ++){
if(!v[i]){
prime[top ++] = i;
for(int j = i + i;j < maxn;j += i){
v[j] = true;
}
}
}
}
int main(){
int t;
int ca = 1;
scanf("%d",&t);
init();
while(t --){
long long a,b;
bool can = true;
scanf("%I64d%I64d",&a,&b);
for(int i = 0;i < top && prime[i] * prime[i] <= a;i ++){
if(a % prime[i] == 0){
if(b % prime[i] != 0){
can = false;
break;
}
else {
while(a % prime[i] == 0){
a /= prime[i];
}
}
}
}
if(a > 1)if(b % a != 0)can = false;
if(!can)printf("Case #%d: NO\n",ca ++);
else printf("Case #%d: YES\n",ca ++);
}
return 0;
}