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

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