给你两个整数 ，求满足 x\mid p,q\nmid x 的最大整数 x。
解题思路
数学方面的题目是真的不会啊。。
上次就一道1e18分解质数的题目就卡住我了。
易知，当q\nmid p的时候，答案就是p。
当q\mid p的时候，首先可以把p和q按质数乘形式表示出来，p=p_1^{\alpha_1}p_2^{\alpha_2}····p_s^{\alpha_s} 和 q=p_1^{\beta_1}p_2^{\beta_2}····p_s^{\beta_s} ，由 p\mid q知\alpha_i\geq \beta_i(1\leq i\leq s) ，设x=p_1^{\gamma_1}p_2^{\gamma_2}····p_s^{\gamma_s} ，由x\mid p,q\nmid x知所有\alpha_i\geq \gamma_i 且并非所有\gamma_i\geq \beta_i ，即只需要枚举一个质因数，并取他的n-1次方，取所有结果的最大值即可，故 ![[公式]](https://www.zhihu.com/equation?tex=x_%7Bmax%7D%3D%5Cmax_%7B1%5Cle+i%5Cle+s%2C%5Cbeta_i%5Cne0%7D%7Bp_1%5E%7B%5Calpha_1%7Dp_2%5E%7B%5Calpha_2%7D%5Ccdots+p_%7Bi-1%7D%5E%7B%5Calpha_%7Bi-1%7D%7Dp_i%5E%7B%5Cbeta_i-1%7Dp_%7Bi%2B1%7D%5E%7B%5Calpha_%7Bi%2B1%7D%7D%7D%5Ccdots+p_s%5E%7B%5Calpha%7Bs%7D%7D)
，遍历 q的所有素因子p_i即可。
枚举q的质因数只需要从1枚举到sqrt(q)即可，每次计算一小一大两个因数，取结果最大值。
完整代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
ll p, q;
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
ll div(int x) {
if (x == 1) return 1;
ll t = p;
while (t % q == 0) t /= x;
return t;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
cin >> p >> q;
if (p % q) cout << p << endl;
else {
ll ans = 1;
rep(i, 1, sqrt(q)) {
if (q % i == 0) {
ans = max(ans, div(i)), ans = max(ans, div(q / i));
}
}
cout << ans << endl;
}
}
return 0;
}
|
