526互联

C. Division

发布时间 2023-06-24 00:30:37作者: margo882

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.

思路：

由于p过大，因此不能对p进行质因子分解或者因子分解各种操作。

着眼于 p%x =0  和 x%q !=0  ，我们可以知道，当 p%q !=0 时，我们直接取 x = p是符合条件的。

考虑 p%q =0 时，x是p的一个因数，而不是q的倍数，但是q是p的一个因数

此时我们要求最大的x，我们对q的因数进行分解，然后对每个因数考虑 x不取该因数但是仍是q的因数，这样x与p会相差这个因数的关系导致 x%q !=0

对每个因数产生的答案来更新最终答案即可。

 1 #include <bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define mm(a,b) memset(a,b,sizeof(a))
 5 #define PI acos(-1)
 6 #define int long long
 7 #define no cout<<"NO\n";
 8 #define yes cout<<"YES\n";
 9 using namespace std;
10 typedef long long LL;
11 typedef pair<int, int> PII;
12 const int N = 1e6;
13 const int mod=1e9+7;
14 int n,m;
15 signed main()
16 {
17     ios::sync_with_stdio(false);
18     cin.tie(0),cout.tie(0);
19     int T=1;
20     cin>>T;
21     while(T--)
22     {
23         int p,q;
24         cin>>p>>q;
25         map<int,int>mp;
26         if(p%q!=0)
27         {
28             cout<<p<<"\n";
29         }
30         else
31         {
32             int x=q;
33             int ans=0;
34             for(int i=1;i*i<=q;i++)
35             {
36                 if(q%i)continue;
37                 int res=p;
38                 if(i!=1)
39                 {
40                     while(res%q==0)
41                         res/=i;
42                     ans=max(ans,res);
43                 }
44                 res=p;
45                 while(res%q==0)
46                 {
47                     res/=(q/i);
48                 }
49                 ans=max(ans,res);
50             }
51             cout<<ans<<"\n";
52         }
53     }
54     return 0;
55 }