本文共 1980 字，大约阅读时间需要 6 分钟。

C. Division

time limit per test1 second

memory limit per test512 megabytes

input standard input

output standard output

Oleg’s favorite subjects are

History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers

pi and qi and for each pair decided to find the greatest integer xi,

such that:

pi is divisible by xi; xi is not divisible by qi. Oleg is really good

at division and managed to find all the answers quickly, how about

you? Input The first line contains an integer t (1≤t≤50) — the number

of pairs.

Each of the following t lines contains two integers pi and qi

(1≤pi≤1018; 2≤qi≤109) — the i-th pair of integers.

Output Print t integers: the i-th integer is the largest xi such that

pi is divisible by xi, but xi is not divisible by qi.

One can show that there is always at least one value of xi satisfying

the divisibility conditions for the given constraints.

题意：给两个数p,q，求出最大的数x使得(p%x=0)且(q%x!=0)

#pragma GCC optimize("Ofast")#pragma GCC target("avx,avx2,fma")#pragma GCC optimization ("unroll-loops")#include
   
    #define int long longusing namespace std;signed main(){       ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);    int _;    cin >> _;    while(_--)    {           int p, q;        int ans;        ans=0;        cin >> p >> q;        if(p % q != 0)cout << p << endl;        else        {               int tmp;            for(int i=1;i*i<=q;i++){                   if(q%i==0){                   if(i!=1){                       tmp=p;                    while(tmp%q==0){                           tmp/=i;                    }                    ans=max(ans,tmp);                }                tmp=p;                while(tmp%q==0){                       tmp/=q/i;                }                ans=max(ans,tmp);            }            }            cout<
    
     <