fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1429432;
  5. int tree[MX], Ans[MX];
  6.  
  7.  
  8. void update(int x, int delta){ 
  9. 	for(; x < MX ; tree[x] += delta, x += x & -x); 
  10. }
  11.  
  12. int query(int x){
  13. 	int sum = 0;
  14. 	for(; x > 0 ; sum += tree[x], x -= x & -x);
  15. 	return sum;
  16. }
  17.  
  18. int kth(int x){
  19. 	int lo = 0, hi = MX, mid;
  20. 	for(; hi - lo > 1 ;){
  21. 		mid = (lo + hi) >> 1;
  22. 		int k = query(mid);
  23. 		(k >= x) ? hi = mid : lo = mid;
  24. 	}
  25. 	return hi;
  26. }
  27.  
  28. void pre_process(){
  29. 	int cnt = 1;
  30. 	for(int i = 1; i < MX; update(i, 1), i += 2);
  31.     Ans[0] = 1;
  32. 	for(int i = 2; i < MX; i++){
  33. 		int num = kth(i);
  34. 		Ans[cnt++] = num;
  35.  
  36. 		int del = 0;
  37. 		for(int j = num; j < MX; j += num){
  38. 			int val = kth(j - del);
  39. 			update(val, -1);
  40. 			del++;
  41. 		}
  42. 	}
  43. }
  44.  
  45. int main() {
  46. 	pre_process();
  47. 	int t, n;
  48.  
  49. 	scanf("%d", &t);
  50. 	for(int i = 1; i <= t; i++){
  51. 		scanf("%d", &n);
  52. 		printf("Case %d: %d\n", i, Ans[n - 1]);
  53. 	}
  54. 	return 0;
  55. }
Success #stdin #stdout 0.66s 14640KB
comments (?)
stdin
copy 
3
5
6
7
stdout
copy 
Case 1: 13
Case 2: 15
Case 3: 21
https://ideone.com/MF0yjB
language:
C++14 (gcc 8.3)
created:
8 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!