A. Division

题意 给定p和q，找一个最大的x，x能整除p，但是q不能整除x

分析

x肯定是p的唯一分解定理的一部分，所以可以考虑从x中删除一下，使得q整除x。由于p太大，分解它肯定会超时，所以可以分解q，然后看q的每一个质因数的次方，p的这个质因数次方是否都小于它。如果都小于它，那么答案就是p，否则就让某个质数的次方，让p这边小于q（这里暴力一下就行）

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------

int T;
ll a,b;
int P[maxn],tail;
bool vis[maxn];
map<int,int> mp;
ll A,B;
void initP(int N){
    vis[1] = 1;
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;j<tail && P[j] <= N/i;j++){
            vis[P[j] * i] = 1;
            if(i % P[j] == 0) break;
        }
    }
}
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res * a;
        b>>=1;
        a*=a;
    }
    return res;
}
void solve(){
    read(A,B);
    ll a = A,b = B;
    mp.clear();
    for(int i = 0;i<tail && P[i] * P[i]<=b;i++){
        if(b % P[i] == 0){
            int cnt = 0;
            while(b % P[i] == 0){
                cnt ++;
                b/=P[i];
            }
            mp[P[i]] = cnt;
        }
    }
    if(b > 1) mp[b] = 1;

    int find = 0;
    for(auto pp:mp){
        ll p = pp.fs,cnt = pp.sc;
        ll coun = 0,a = A;
        while(a%p == 0){
            coun++;
            a/=p;
        }
        if(coun < cnt){
            find = 1;
            break;          
        }
    }
    if(find){
        printf("%lld\n",A);
    }else{
        ll ans = 0;
        for(auto pp:mp){
            ll p = pp.fs,cnt = pp.sc;
            ll coun = 0,a = A;
            while(a%p == 0){
                coun++;
                a/=p;
            }
            if(coun >= cnt){
                ans = max(ans,A/ksm(p,coun - cnt + 1));
            }
        }
        printf("%lld\n",ans);
    }
}
int main(){
    // debug_in;

    initP(1000000);
    read(T);
    while(T--){
        solve();
    }


    return 0;
}