题目思路:
- 当 p < q p<q p<q 时,显然答案是 p p p;
- 当 p ≥ q p\ge q p≥q 时,如果 p % q ≠ 0 p\%q \ne0 p%q=0,显然答案是 p p p;
- 当 p ≥ q p\ge q p≥q 时,且 p % q = 0 p\% q = 0 p%q=0,想到唯一分解定理,把 p p p, q q q 拆成若干的素数相乘,当 p p p 减少若干个 q q q 的质因子,满足不能被 q q q 整除时即可得到我们要的答案。观察到 q q q 比较小,所以去找 q q q 的质因子。
参考代码:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int main() {
int t;
cin >> t;
while (t--) {
ll p, q;
cin >> p >> q;
if (p < q) cout << p << endl;
else {
if (p % q != 0) {
cout << p << endl;
} else {
vector<ll> v;
ll x = sqrt(q);
ll tmp = q, ans = -1;
for (int i = 2; i <= x; i++) {
if (tmp % i == 0) {
v.push_back(i);
while (tmp % i == 0) tmp /= i;
}
}
if (tmp > 1) v.push_back(tmp);
for (int i = 0; i < v.size(); i++) {
tmp = p;
while (tmp % q == 0) tmp /= v[i];
ans = max(ans, tmp);
}
cout << ans << endl;
}
}
}
}