fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #include<bits/stdc++.h>
  3. #define ull unsigned long long
  4. #define ll long long
  5. #define all(x) x.begin(), x.end()
  6. using namespace std;
  7. const int maxn = 1e7 + 1;
  8. const int N = 5e4 + 1;
  9. bool checkPrime(ll n)
  10. {
  11. 	if (n == 2 || n == 3) return true;
  12. 	if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
  13. 	for (int i = 5; 1ll * i * i <= n; i += 6) {
  14. 		if (n % i == 0 || n % (i + 2) == 0) return false;
  15. 	}
  16. 	return true;
  17. }
  18. vector<int> Prime;
  19. void GenPrime() {
  20. 	Prime.push_back(2);
  21. 	int n = sqrt(2e9);
  22. 	for (int i = 3; i <= n; i += 2) {
  23. 		if (checkPrime(i)) Prime.push_back(i);
  24. 	}
  25. }
  26. bool hoanvi[20];
  27. ll A[N];
  28. void Solve(ll n, ll x) {
  29. 	ll maxn = pow(2, n) - 1;
  30. 	bool check = false;
  31. 	for (int i = 1; i <= maxn; ++i) {
  32. 		for (int it = 1; it <= 19; ++it) hoanvi[i] = false;
  33. 		int tmp = i, j = 0;
  34. 		while (tmp != 0) {
  35. 			++j;
  36. 			hoanvi[j] = (tmp % 2 == 0 ? false : true);
  37. 			tmp /= 2;
  38. 		}
  39. 		ll C1 = 1, C2 = 1;
  40. 		for (int k = 1; k <= n; ++k) {
  41. 			if (hoanvi[k]) {
  42. 				C1 *= A[k];
  43. 			}
  44. 			else {
  45. 				C2 *= A[k];
  46. 			}
  47. 		}
  48. 		if (C2 < C1) swap(C1, C2);
  49. 		if ((C1 - 1 + C2) % 2 == 0) {
  50. 			ll R = (C1 - 1 + C2) / 2;
  51. 			ll L = C2 - R;
  52. 			if (R < x) {
  53. 				cout << L << " " << R;
  54. 				check = true;
  55. 				break;
  56. 			}
  57. 		}
  58. 	}
  59. 	if (!check) {
  60. 		cout << -1;
  61. 	}
  62. }
  63. int main() {
  64. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  65. 	GenPrime();
  66. 	int t;
  67. 	cin >> t;
  68. 	ll x, n = Prime.size();
  69. 	int i = 0, j = 0;
  70. 	while (t--) {
  71. 		for (int it = 1; it <= i; ++it) {
  72. 			A[it] =  0;
  73. 		}
  74. 		i = 0; j = 0;
  75. 		cin >> x;
  76. 		ll motcaigiday = x;
  77. 		x *= 2;
  78. 		while (x != 1 && j < n) {
  79. 			if (x % Prime[j] == 0) {
  80. 				++i;
  81. 				ll value = 1;
  82. 				while (x % Prime[j] == 0) {
  83. 					x /= Prime[j];
  84. 					value *= Prime[j];
  85. 				}
  86. 				A[i] = value;
  87. 			}
  88. 			++j;
  89. 		}
  90. 		if (x != 1) {
  91. 			++i;
  92. 			A[i] = x;
  93. 		}
  94. 		sort(A + 1, A + i + 1);
  95. 		Solve(i, motcaigiday);
  96. 		cout << "\n";
  97. 	}
  98.  
  99. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tyMxJG
language:
C++14 (gcc 8.3)
created:
10 days 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!