fork download 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #include <bits/stdc++.h>
  9. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define pb push_back
  14. #define sz(a) (int)a.size()
  15. #define FILL(a,x) memset(a,x,sizeof(a))
  16.  
  17. using namespace std;
  18. typedef long long ll;
  19. typedef pair<int,int> ii;
  20.  
  21. void addFactors(ll x, map<ll,int> &mp) {
  22.     for(ll p = 2; p * p <= x; ++p)
  23.       if(x % p == 0) {
  24.         int cnt = 0;
  25.         while(x % p == 0) {
  26.             x /= p;
  27.             ++cnt;
  28.         }
  29.         if(cnt % 2 == 1) mp[p] ^= 1;
  30.      }
  31.     if(x > 1) mp[x] ^= 1;
  32. }
  33.  
  34. int main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(NULL); cout.tie(NULL);
  37.     freopen("minsum.inp","r",stdin);
  38.     freopen("minsum.out","w",stdout);
  39.  
  40.     int T;
  41.     cin >> T;
  42.     while(T--) {
  43.         ll a, b;
  44.         cin >> a >> b;
  45.  
  46.         map<ll,int> mp;
  47.         addFactors(a, mp);
  48.         addFactors(b, mp);
  49.  
  50.         vector<ll> primes;
  51.         for(map<ll,int>::iterator it = mp.begin(); it != mp.end(); ++it) {
  52.             if(it->second & 1) primes.pb(it->first);
  53.         }
  54.  
  55.         int m = sz(primes);
  56.         if(m == 0) {
  57.             cout << 1 << " " << 1 << el;
  58.             continue;
  59.         }
  60.  
  61.         ll bestA = -1, bestB = -1;
  62.         ll bestSum = -1;
  63.  
  64.         int lim = 1 << m;
  65.         FOR(mask,0,lim-1) {
  66.             ll x = 1, y = 1;
  67.             for(int i = 0; i < m; ++i) {
  68.                 if(mask & (1 << i)) x *= primes[i];
  69.                 else y *= primes[i];
  70.             }
  71.             ll curSum = x + y;
  72.             if(bestSum == -1 || curSum < bestSum) {
  73.                 bestSum = curSum;
  74.                 bestA = x;
  75.                 bestB = y;
  76.             }
  77.         }
  78.  
  79.         cout << bestA << " " << bestB << el;
  80.     }
  81.  
  82.     return 0;
  83. }
  84.  
  85.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZHYopo
language:
C++14 (clang 8.0)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!