Codeforces 1444A 数学

1444A
题意：找到最大的x，x满足整除p但是不能被q整除；
题解：分为两种情况，假如$p$ $mod$ $q!=0$,结果就是p
剩下一种情况，可以将q分解质因数，枚举每一个质因子，

这种情况下p一定能够被q整除，说明q的所有质因子p里面也有
，并且都大于等于q的质因数的次方，
要是p的因子不能被q整除，则p里面有q的某一个质因数的次方-1，
通过枚举每个质因数得出最大值；

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define x first
#define y second
ll fun(ll s, ll prime, int times) {while (s % prime == 0) {s /= prime;}times--;while (times--) {s = s * prime;}return s;
}
int main() {int t;cin >> t;while (t--) {ll p, q;cin >> p >> q;if (__gcd(p, q) == 1 or p % q != 0) cout << p << endl;else {map<ll, int> mp;for (ll i = 2; i <= q / i; i++) {while (q % i == 0) {mp[i]++;q /= i;}}if (q > 1) mp[q]++;ll res = 0;for (auto i : mp) {ll sum = fun(p, i.x, i.y);res = max(res, sum);}cout << res << endl;}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！