HDU 4320 Arcane Numbers 1 (数论)

A - 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.

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

Sample Output

Case #1: YES

Case #2: NO

Case #3: YES

对于A进制的一个数，先将其左移N位使得其成为一个整数，然后再将这个整数化为B进制的一个数，

然后我们只需要考虑这个数是否能够整除A^N即可（因为我们前面左移了N位），我可以将B进制的

这个数先进行左移无限位，那么当有A^N 整除 B^INF 时我们就可以将这个除尽，然后我们再将B

右移INF位便可以了。

这里就把问题转化为了A^N能够整除B^INF进制了，进一步我们可以得到B包含所有A的质因子便为判定条件了。

#include <iostream>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
const int maxn=1000100;
bool isprime[maxn];
int prime[maxn];
using namespace std;
int i,j,k=0;
void pr()
{
    for(i=2;i<=maxn;i++)
    {
        if(!isprime[i])
        {
            for(j=i+i;j<=maxn;j=j+i)
            isprime[j]=true;
            prime[k++]=i;
        }
    }
}
int main()
{
    pr();
    int t,c=1;
    bool flag=true;
    long long a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        flag=true;
        for(i=0;i<k&&prime[i]<=a;i++)
        {
            if(a%prime[i]==0)
            {
                if(b%prime[i]!=0)
                {
                    flag=false;
                    break;
                }
            }
            while(a%prime[i]==0)
            a/=prime[i];
        }
        if(b%a!=0)
        flag=false;
        if(flag)
        cout<<"Case #"<<c++<<": YES"<<endl;
        else
        cout<<"Case #"<<c++<<": NO"<<endl;
    }
    return 0;
}