fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. int main(){
  5. ios::sync_with_stdio(false);
  6. cin.tie(nullptr);
  7. int T;
  8. if(!(cin >> T)) return 0;
  9. while(T--){
  10. int N;
  11. int64 K;
  12. cin >> N >> K;
  13. // compute denom = 2^{N-1} - 1, but cap it so it doesn't overflow and we only need it relative to K
  14. __int128 pw = 1;
  15. for(int i = 0; i < N-1; ++i){
  16. // try to multiply by 2, but if pw is already huge relative to K, break
  17. if(pw > (__int128)K + 5) { // small margin
  18. break;
  19. }
  20. pw *= 2;
  21. }
  22. __int128 denom = pw - 1;
  23. if(denom <= 0) denom = 1; // safety, though shouldn't happen
  24. // compute a = 1 + ceil(K / denom)
  25. __int128 a_minus1 = ( (__int128)K + denom - 1 ) / denom; // ceil division
  26. int64 a = (int64)(1 + a_minus1);
  27. // construct sequence
  28. vector<int64> A;
  29. A.reserve(N);
  30. A.push_back(a);
  31. int64 rem = K;
  32. for(int i = 1; i <= N-1; ++i){
  33. int64 cur = A.back();
  34. int64 can = cur - 1; // m_i <= A_i -1
  35. int64 take = min(can, rem);
  36. int64 next = cur + take;
  37. A.push_back(next);
  38. rem -= take;
  39. }
  40. // rem must be zero
  41. // output sequence
  42. for(int i = 0; i < N; ++i){
  43. if(i) cout << ' ';
  44. cout << A[i];
  45. }
  46. cout << '\n';
  47. }
  48. return 0;
  49. }
Success #stdin #stdout 0.01s 5276KB
stdin
2
5 3
2 3
stdout
2 3 5 5 5
4 7