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<bits/stdc++.h>
using namespace std;
typedef long long ll ;
ll a , b ;
int main () {
int T ;
scanf ("%d" , &T ) ;
for (int cas = 1 ; cas <= T ; cas ++) {
scanf ("%I64d%I64d" , &a , &b) ;
ll g = __gcd (a,b) ;
if (g == 1) {
printf ("Case #%d: NO\n" , cas) ;
continue ;
}
a/= g ;
ll flag = __gcd (a , g) ;
while (flag != 1) {
while (a % flag == 0) a/=flag ;
flag = __gcd (a , g) ;
}
if (a == 1 ) printf ("Case #%d: YES\n" , cas) ;
else printf ("Case #%d: NO\n" , cas) ;
}
return 0 ;
}
其实用O（sqrt（n））的方法也是可以的，但姿势不好看很容易tle。
用log（n)的方法理解上也很容易，先求g = gcd(a , b) ,那么显然若 {a的质因子 } 属于 {g的质因子} ， a^k % b 一定等于0 ------no.1
所以之后不断求 flag = gcd (g , a) , 并让 a /= flag ；
最终a 和 g互质时，若a != 1 , 则no.1肯定不成立，那么肯定不存在k，能让所求等式成立，
反之a = 1的情况，就肯定成立了。