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 }
- Divisionpermutation division atcoder regular division integer 288f abc division 1916f group cf square-free codeforces division version codeforces division 1916f group starters division rated 109 permutation division 114f arc codechef starters division报告 infrastructure information programming division 线段division性质159f