2012多校3.A（用O(log(n))判断b^k % a == 0）

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

#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的情况，就肯定成立了。

巴特西

2012多校3.A（用O(log(n))判断b^k % a == 0）

最新文章

热门文章