Advertisement
Saleh127

CF 1445C

Nov 1st, 2020
61
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. ll p,q;
  7.  
  8. ll div(ll x)
  9. {
  10. if(x==1) return 1;
  11. ll s=p;
  12. while(s%q==0)
  13. {
  14. s/=x;
  15. }
  16. return s;
  17. }
  18.  
  19. int main()
  20. {
  21. ios_base::sync_with_stdio(0);
  22. cin.tie(0);
  23. cout.tie(0);
  24. test
  25. {
  26. cin>>p>>q;
  27. if(p%q==0)
  28. {
  29. ll ans=1;
  30. for(ll i=1;i*i<=q;i++)
  31. {
  32. if(q%i==0)
  33. {
  34. ans=max(ans,div(i));
  35. ans=max(ans,div(q/i));
  36. }
  37. }
  38. cout<<ans<<endl;
  39. }
  40. else cout<<p<<endl;
  41.  
  42. }
  43.  
  44.  
  45.  
  46. return 0;
  47. }
  48.  
Advertisement
RAW Paste Data Copied
Advertisement