首页 > ACM题库 > HDU-杭电 > HDU 4320-Arcane Numbers 1[解题报告]HOJ
2015
05-23

HDU 4320-Arcane Numbers 1[解题报告]HOJ

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;
}