fork download
copy 
  1. /* by Neptune*/
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <sstream>
  7. #include <cstring>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. #include <stack>
  13. #include <cmath>
  14. #include <iomanip>
  15. #include <unordered_map>
  16. #include <cstdlib>
  17. #include <bitset>
  18. #include <numeric>
  19. #include <unordered_set>
  20. using namespace std;
  21.  
  22. #define faster() ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  23.  
  24. int x[100] = { 0 };
  25. vector<int> v;
  26. vector<int> ans;
  27.  
  28. bool chiahet(vector<int> v, vector<int> u, int n) {
  29. 	ans.clear();
  30. 	while (true) {
  31. 		int d = v[0] - u[0];
  32. 		ans.push_back(d);
  33.  
  34. 		vector<int> c;
  35. 		for (int i = 0; i < u.size(); i++) {
  36. 			c.push_back(u[i] + d);
  37. 		}
  38.  
  39. 		int i = 0;
  40. 		int j = 0;
  41. 		vector<int> res;
  42. 		while (i < v.size() && j < c.size()) {
  43. 			if (v[i] == c[j]) {
  44. 				i++;
  45. 				j++;
  46. 			}
  47. 			else if (v[i] < c[j]) {
  48. 				res.push_back(c[j]);
  49. 				j++;
  50. 			}
  51. 			else if (v[i] > c[j]) {
  52. 				res.push_back(v[i]);
  53. 				i++;
  54. 			}
  55. 		}
  56. 		while (i < v.size()) res.push_back(v[i++]);
  57. 		while (j < c.size()) res.push_back(c[j++]);
  58.  
  59. 		sort(res.begin(), res.end(), greater<int>());
  60. 		v = res;
  61. 		if (v.empty()) return true;
  62. 		if (!v.empty() && v[0] < u[0]) return false;
  63. 	}
  64. }
  65.  
  66. void kiemtra(int n) {
  67.  
  68. 	vector<int> u;
  69. 	u.push_back(n + 1);
  70. 	for (int i = n; i >= 1; i--) {
  71. 		if (x[i]) u.push_back(i);
  72. 	}
  73. 	u.push_back(0);
  74. 	while (!v.empty() && chiahet(v, u, n)) {
  75. 		v = ans;
  76. 		for (auto x : u) {
  77. 			if (x == 0) cout << 1;
  78. 			else
  79. 				if (x == 1) cout << "x + ";
  80. 				else
  81. 					cout << "x^" << x << " + ";
  82. 		}
  83. 		cout << endl;
  84. 	}
  85. }
  86.  
  87. void sinh_nhi_phan(int i, int n) {
  88. 	if (v.empty()) return;
  89. 	for (int j = 0; j <= 1; j++) {
  90. 		x[i] = j;
  91. 		if (i == n) kiemtra(n);
  92. 		else sinh_nhi_phan(i + 1, n);
  93. 	}
  94. }
  95. int main() {
  96. 	cout << "Phan tich x^n + 1 thanh cac da thuc bat kha quy\n";
  97. 	cout << "Nhap n: ";
  98. 	int n;
  99. 	cin >> n;
  100.  
  101. 	v.push_back(n);
  102. 	v.push_back(0);
  103.  
  104. 	for (int i = 1; i <= n - 1; i++) {
  105. 		if (v[0] == 0) break;
  106. 		if (i >= 2) sinh_nhi_phan(1, i - 1);
  107. 		else if (i == 1) kiemtra(0);
  108. 	}
  109.  
  110. 	//for (auto x : v) cout << x << " - ";
  111.  
  112. 	return 0;
  113. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
15
stdout
copy 
Phan tich x^n + 1 thanh cac da thuc bat kha quy
Nhap n: x + 1
x^2 + x + 1
x^4 + x^3 + 1
x^4 + x + 1
x^4 + x^3 + x^2 + x + 1
https://ideone.com/muUQW7
language:
C++ (gcc 8.3)
created:
11 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!