求估分和算时间复杂度

#include<bits/stdc++.h>
using namespace std;
unsigned long long gcd(unsigned long long a,unsigned long long b){
    unsigned long long r;
    while(b>0){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}
bool check(unsigned long long x,unsigned long long y,unsigned long z){
    if(gcd(x,y)*y==z) return true;
    else return false;
}
int main(){
    freopen("math3.in","r",stdin);
    freopen("math.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        vector<unsigned long long> vec;
        unsigned long long a,z;
        scanf("%llu %llu",&a,&z);
        z/=a;
        for(unsigned long long i(1);i<=sqrt(z);++i){
            if(z%i==0){
                vec.push_back(i);
                if(i*i != z) vec.push_back(z/i);
            }
        }
        unsigned long long mn = 18446744073709551615ULL;
        bool fl = false;
        for(auto x:vec){
            if(x>mn) continue;
            if(check(a,x,z)){
                mn = mn > x ? x : mn;
                fl = true;
            }
        }
        if(fl) printf("%llu\n",mn);
        else printf("%d\n",-1);
    }
    return 0;
}