CFR-680C Division 题解

题目大意

给你两个整数$p,q(1\leq p\leq10^{18},2\leq q\leq 10^9)$ ，求满足 $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次方，取所有结果的最大值即可，故 ，遍历$ q$的所有素因子$p_i$即可。

枚举$q$的质因数只需要从1枚举到$sqrt(q)$即可，每次计算一小一大两个因数，取结果最大值。

完整代码

#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);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	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;
}