fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. const int NMAX = 30000;
  9.  
  10. #define FOR(i,a,b) for(int i=a;i<b;i++)
  11. #define REP(i,b) FOR(i,0,b)
  12.  
  13. typedef long long ll;
  14.  
  15. int n, m;
  16.  
  17. int coeff[NMAX];
  18. void InitCoeff(){
  19. 	for (int i = n + 1; i >= 2; i--){
  20. 		coeff[i - 2] = 1;
  21. 		for (int j = i * 2; j <= n+1; j += i){
  22. 			coeff[i-2] -= coeff[j - 2];
  23. 		}
  24. 	}
  25. }
  26.  
  27. struct frac{
  28. 	ll num;
  29. 	ll den;
  30. 	bool operator<(const frac& rhs) const{
  31. 		ll a = num * rhs.den;
  32. 		ll b = rhs.num * den;
  33. 		return a < b;
  34. 	}
  35. 	bool operator>(const frac& rhs) const{
  36. 		ll a = num * rhs.den;
  37. 		ll b = rhs.num * den;
  38. 		return a > b;
  39. 	}
  40. 	bool operator==(const frac& rhs) const{
  41. 		ll a = num * rhs.den;
  42. 		ll b = rhs.num * den;
  43. 		return a == b;
  44. 	}
  45. 	frac operator+(const frac& rhs) const{
  46. 		ll a = num * rhs.den;
  47. 		ll b = rhs.num * den;
  48. 		return{ a + b, den*rhs.den };
  49. 	}
  50. 	frac operator-(const frac& rhs) const{
  51. 		ll a = num * rhs.den;
  52. 		ll b = rhs.num * den;
  53. 		return{ a - b, den*rhs.den };
  54. 	}
  55. };
  56.  
  57. const ll B = 1000000007;
  58. ll count(frac f, frac l){
  59. 	frac a = f - l;
  60. 	a.num = max(a.num, 0LL);
  61. 	frac b = f + l;
  62. 	b.num = min(b.num, b.den - 1);
  63. 	ll ret = 0;
  64. 	FOR(i, 2, n + 2){
  65. 		ret -= ((a.num*i) / a.den)*coeff[i - 2];
  66. 		ret += ((b.num*i) / b.den)*coeff[i - 2];
  67. 	}
  68. 	return ret;
  69. }
  70.  
  71. int main(){
  72. 	scanf("%d%d", &n, &m);
  73. 	InitCoeff();
  74. 	REP(_, m){
  75. 		frac s;
  76. 		ll k;
  77. 		scanf("%lld%lld%lld", &s.num, &s.den, &k);
  78. 		ll l = 1, r = B;
  79. 		while (r - l > 1)
  80. 		{
  81. 			ll c = count(s, { (l + r) / 2, B });
  82. 			if (c == k){
  83. 				l = (l + r) / 2;
  84. 				break;
  85. 			}
  86. 			else if (c < k){
  87. 				l = (l + r) / 2;
  88. 			}
  89. 			else{
  90. 				r = (l + r) / 2;
  91. 			}
  92. 		}
  93. 		frac maxdist = s;
  94. 		frac dif = { 0, 1 };
  95. 		frac a = s - frac{ l, B };
  96. 		a.num = max(a.num, 0LL);
  97. 		frac b = s + frac{ l, B };
  98. 		b.num = min(b.num, b.den - 1);
  99. 		FOR(i, 2, n + 2){
  100. 			frac f = { ((a.num*i) / a.den) + 1, i };
  101. 			if (s - f > dif){
  102. 				dif = s - f;
  103. 				maxdist = f;
  104. 			}
  105. 			f = { ((b.num*i) / b.den), i };
  106. 			if (f - s > dif){
  107. 				dif = f - s;
  108. 				maxdist = f;
  109. 			}
  110. 		}
  111. 		printf("%lld\n", maxdist.den - 1);
  112. 	}
  113. }
Success #stdin #stdout 0s 3576KB
comments (?)
stdin
copy 
7 5
3 8 7
2 5 12
4 8 7
1 5 13
3 5 6
stdout
copy 
1
5
7
4
6
https://ideone.com/NCx4Iz
language:
C++ (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!