fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6.  
  7. string solve(ll p)
  8. {    
  9. 	ll a = 1, b = 1, m = p/2; bool found = false; 
  10.  
  11.     if (p == 2)
  12.     	found = true;
  13.  
  14. 	const auto square = [](ll l2, ll& l)
  15.     {    
  16.         l = sqrt(l2); return l*l == l2;
  17.     };
  18.  
  19.     if (not found and m%2 == 0)
  20.         for (ll k = 0, l, l2, q = m/2; (l2 = q-k*(k+1)) > 0; ++k)
  21.             if (square(l2,l))
  22.             {
  23.                 if ((a = 2*k+1) > (b = 2*l))
  24.                     swap(a,b);
  25.  
  26.                 found = true; break; 
  27.             }
  28.  
  29.     return found ? to_string(a) + ' ' + to_string(b) : "Impossible";
  30. }
  31.  
  32. int main() 
  33. {
  34.     int T; vector<ll> P; set<ll> query; map<ll,string> answer;  
  35.  
  36.     ios_base::sync_with_stdio(false), 
  37.     cin.tie(nullptr), cout.tie(nullptr), 
  38.     cin >> T, P.resize(T);
  39.  
  40.     for (int i = 0; i < T; ++i)
  41.         cin >> P[i], query.insert(P[i]);
  42.  
  43.     for (auto p: query)
  44.         answer[p] = solve(p); 
  45.  
  46.     for (int i = 0, j = 1; i < T; i = j++)
  47.         cout << "Case " << j << ": " << answer[P[i]] << '\n';
  48. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
2
11
13
stdout
copy 
Case 1: 1 1
Case 2: Impossible
Case 3: 2 3
https://ideone.com/fblLp7
Squared Sum Prime
language:
C++14 (gcc 8.3)
created:
5 years 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!