C. Division

C. Division

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 \(p_i\) and \(q_i\) and for each pair decided to find the greatest integer \(x_i\), such that:

  • \(p_i\) is divisible by \(x_i\);
  • \(x_i\) is not divisible by \(q_i\).

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 \le t \le 50\)) — the number of pairs.

Each of the following \(t\) lines contains two integers \(p_i\) and \(q_i\) (\(1 \le p_i \le 10^{18}\); \(2 \le q_i \le 10^{9}\)) — the \(i\)-th pair of integers.

Output

Print \(t\) integers: the \(i\)-th integer is the largest \(x_i\) such that \(p_i\) is divisible by \(x_i\), but \(x_i\) is not divisible by \(q_i\).

One can show that there is always at least one value of \(x_i\) satisfying the divisibility conditions for the given constraints.

样例

1
2
3
4
5
6
7
8
9
10
输入:
3
10 4
12 6
179 822
输出:
10
4
179

算法1

分解质因数
image-20241002225028721

参考文献

参考 #### C++ 代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;

int t;

vector<int> div(ll x)//质因数分解
{
	vector<int> res;
	for(ll i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			res.push_back(i);
			while(x%i==0)
				x/=i;
		}
	}
	if(x!=1) res.push_back(x);
	return res;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
       ll p,q;
       scanf("%lld%lld",&p,&q);
       if(p%q!=0)
       {
       	printf("%d\n",p);
       	continue;
	   }
       vector<int >a = div(q);//获取q的所有质因数
       ll res=1;
       for(int i=0;i<a.size();i++)//遍历q的全部因数
       {
       	 ll k=p;
       	 while(k%q==0)//如果剩下的数能被q整除 说明还有a[i]这个因数
       	 {
       	 	k/=a[i];
		 }
		 res=max(res,k);
	   }
	   printf("%lld\n",res);
    }
    return 0;
}