codeforces Round680 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
t
t pairs of integers
p
i
p_i
pi and
q
i
q_i
qi and for each pair decided to find the greatest integer
x
i
x_i
xi, such that:
-
p
i
p_i
pi is divisible by
x
i
x_i
xi;
-
x
i
x_i
xi is not divisible by
q
i
q_i
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
t
t
(
1
≤
t
≤
50
)
(1≤t≤50)
(1≤t≤50) — the number of pairs.
Each of the following
t
t
t lines contains two integers
p
i
p_i
pi and
q
i
q_i
qi
(
1
≤
p
i
≤
1
0
18
;
2
≤
q
i
≤
1
0
9
)
(1≤ p_i≤10^{18}; 2≤q_i≤10^9)
(1≤pi≤1018;2≤qi≤109)— the
i
−
t
h
i-th
i−th pair of integers.
Output
Print
t
t
t integers: the
i
−
t
h
i-th
i−th integer is the largest
x
i
x_i
xi such that
p
i
p_i
pi is divisible by
x
i
x_i
xi, but
x
i
x_i
xi is not divisible by
q
i
q_i
qi.
One can show that there is always at least one value of
x
i
x_i
xii satisfying the divisibility conditions for the given constraints.
Example
input
3
10 4
12 6
179 822
output
10
4
179
Note
For the first pair, where
p
1
=
10
p_1=10
p1=10 and
q
1
=
4
q_1=4
q1=4, the answer is
x
1
=
10
x_1=10
x1=10, since it is the greatest divisor of
10
10
10 and
10
10
10 is not divisible by
4
4
4.
For the second pair, where
p
2
=
12
p_2=12
p2=12 and
q
2
=
6
q_2=6
q2=6, note that
-
12
12
12 is not a valid
x
2
x_2
x2, since
12
12
12 is divisible by
q
2
=
6
q_2=6
q2=6;
-
6
6
6 is not valid
x
2
x_2
x2 as well:
6
6
6 is also divisible by
q
2
=
6
q_2=6
q2=6.
The next available divisor of
p
2
=
12
p_2=12
p2=12 is
4
4
4, which is the answer, since
4
4
4 is not divisible by
6
6
6.
题意
找一个最大的
x
x
x，满足
p
%
x
=
=
0
a
n
d
x
%
q
!
=
0
p\ \%\ x == 0 \ and\ x\ \%\ q != 0
p % x==0 and x % q!=0。
思路
质因数分解
-
p
%
q
!
=
0
p\ \%\ q\ !=\ 0
p % q != 0，
x
=
p
x = p
x=p
-
p
%
q
=
0
p\ \%\ q\ =\ 0
p % q = 0 , 那么
p
p
p一定包含
q
q
q的所有质因数分解的结果。
举例：
p
=
12
q
=
6
p = 12\ \ q = 6
p=12 q=6
p
=
2
2
∗
3
1
p = 2^2 * 3^1
p=22∗31
q
=
2
1
+
3
1
q = 2^1 +3^1
q=21+31
要使
p
%
q
!
=
0
p\ \%\ q\ !=\ 0
p % q != 0, 只要使
p
p
p 将质因数
2
2
2降幂到
0
0
0(也就是q的质因数
2
2
2的次幂之下)，或者将
3
3
3 的幂降到
0
0
0。
所以，我们只需要枚举
q
q
q的质因子, 找权值最小的，即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 2e5 + 10;
int ans[maxn];
void solve(){
ll p, q;
cin >> p >> q;
if(p % q) {
cout << p << endl;
return;
}
ll ans = 0;
for (ll i = 1; i * i <= q; i++){
if(q % i) continue;
ll t = p;
if(i != 1){
while(t % q == 0) t /= i;
ans = max(ans, t);
}
t = p;
while(t % q == 0) t /= (q / i);
ans = max(ans, t);
}
cout << ans << endl;
}
int main(){
IOS; int t; cin >> t;
while(t--){
solve();
}
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
