Codeforces Round #680 (Div. 2, based on Moscow Team Olympiad) 1445C. Division Solution

 Problem Link: https://codeforces.com/problemset/problem/1445/C

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. #define ll long long
9. using namespace std;
10. ll fun(ll a, ll v, ll b) {
11. if (v == 1) return 1;
12. while (a % b == 0) a /= v;
13. return a;
14. }
15.  
16. int main() {
17. int t;
18. cin >> t;
19. while (t--) {
20. ll p, q;
21. cin >> p >> q;
22. if (p % q != 0) {
23. cout << p << endl;
24. continue;
25. }
26. ll ans = 1;
27. for (ll i = 1; i * i <= q; i++) {
28. if (q % i == 0) {
29. ans = max(ans, fun(p, i, q));
30. ans = max(ans, fun(p, q / i, q));
31. }
32. }
33. cout << ans << endl;
34. }
35. }