Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<map>
  5. #include<set>
  6. #include<string>
  7. #include<cmath>
  8. #include<cstring>
  9.  
  10. using namespace std;
  11.  
  12. long long gcd(long long a, long long b)
  13. {
  14. return b ? gcd(b, a % b) : a;
  15. }
  16.  
  17. vector <pair<int, int>> B;
  18. int zeros, ones;
  19. int ans[100];
  20. multimap<int, int>A;
  21. int len;
  22.  
  23. void solve(int num, int ind, int cnt)
  24. {
  25. if (num == 1)
  26. {
  27. if (ones >= cnt)
  28. {
  29. while (len != 0)
  30. {
  31. cout << A.find(ans[len - 1])->second << " ";
  32. A.erase(A.find(ans[len-1]));
  33. len--;
  34. }
  35. while (cnt > 0)
  36. {
  37. cout << A.find(1)->second << " ";
  38. A.erase(A.find(1));
  39. cnt--;
  40. }
  41. exit(0);
  42. }
  43. return;
  44. }
  45. for (int i = ind; i < B.size() && num%B[i].first==0; ++i)
  46. {
  47. int tmp = B[i].first;
  48. int count = 0;
  49. for (int j = 0; j < B[i].second; ++j)
  50. {
  51. if (num%tmp==0)
  52. {
  53. ans[len++] = tmp;
  54. count++;
  55. solve(num / tmp, i + 1, cnt - j - 1);
  56.  
  57. }
  58. tmp *= B[i].first;
  59. }
  60. len -= count;
  61. }
  62.  
  63. }
  64.  
  65. int main()
  66. {
  67. int n, m, k;
  68. cin >> n >> m >> k;
  69.  
  70. int tmp;
  71. for (int i = 0; i < n; ++i)
  72. {
  73. scanf("%d", &tmp);
  74. A.insert(make_pair(tmp, i + 1));
  75. if (tmp == 0) zeros++;
  76. if (tmp == 1) ones++;
  77. }
  78. tmp = 0;
  79. for (auto i : A)
  80. {
  81. if (i.first > 1)
  82. {
  83. if (tmp != i.first)
  84. {
  85. B.push_back(make_pair(i.first, 1));
  86. tmp = i.first;
  87. }
  88. else
  89. {
  90. B[B.size() - 1].second++;
  91. }
  92. }
  93. }
  94. if (m == 0)
  95. {
  96. for (auto i : A)
  97. {
  98. cout << i.second<<" ";
  99. k--;
  100. if (k == 0) return 0;
  101. }
  102.  
  103. }
  104. solve(m, 0, k);
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement