cf - 1444A - Division

1444A - Division

// 求 一个最大的x,x 满足 是 p 的约数，不是q的倍数
1. p < q || p % q != 0,显然 p 就是答案
2. 对于p % q == 0的情况，朴素想法是求出p的所有约数
然后寻找最大的不能被q整除的数。然后p的范围太大。
所以转而分解q。
3.q = a1 ^ x1 * a2 ^ x2 * ... ^ an * xn.
因为p是q的倍数。所以p = x * a1 ^ y1 * a2 ^ y2 * ... * an ^ yn
其中(y1 >= x1,y2 >= x2,yn >= xn)
因而只要 y1 < x1 || y2 < x2 || ... || yn < xn,必然这个约数是不能
被 q整除的.又要p最大。所以 y1 == x1 - 1,y2 == x2 - 1...yn == xn - 1.
找到其中的最大值即可

#includeusing namespace std;
typedef long long ll;
int main()
{int t;cin >> t;while(t --){ll p;int q;cin >> p >> q;if(p < q || p % q != 0) cout << p << endl;else{ll ans = 0;int t = q;for(int i = 2; i * i <= q; i ++){int f = 0;while(q % i == 0){q /= i;f ++;}if(f){f = f - 1;ll t = p;if(t % i == 0){while(t % i == 0) t /= i;while(f --) t *= i;ans = max(t,ans);}}}if(q > 1) {while(p % q == 0) p /= q;ans = max(p,ans);}cout << ans << endl;}}
}

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