fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned long long ull;
  7. typedef __uint128_t uLL;
  8. typedef unsigned int uint;
  9.  
  10. namespace ds {
  11. 	namespace stac {
  12. 		const int N = 100005;
  13. 		uint qu[N][2]; int qr;
  14. 		void pop () { qr --; }
  15. 		void push (uint x, uint y) { qr ++; qu[qr][0] = x; qu[qr][1] = y; }
  16. 		void top (uint &x, uint &y) { x = qu[qr][0]; y = qu[qr][1]; }
  17. 	}
  18. 	using stac :: push;
  19. 	using stac :: pop;
  20. 	using stac :: top;
  21.  
  22. 	uLL solve (ull n) {
  23. 		uLL ret = 0;
  24. 		ull w = pow (n, 0.35), v = sqrtl (n), x, y;
  25. 		uint dx, dy, ux, uy, mx, my;
  26. 		while (v * v <= n) v ++; while (v * v > n) v --;
  27. 		x = n / v, y = n / x + 1;
  28. 		push (1, 0); push (1, 1);
  29. 		auto outside = [&] (ull x, ull y) { return x * y > n; };
  30. 		auto cut_off = [&] (ull x, uint dx, uint dy) { return (uLL)x * x * dy >= (uLL)n * dx; };
  31. 		while (stac :: qr) {
  32. 			top (dx, dy);
  33. 			while (outside (x + dx, y - dy)) {
  34. 				ret += x * dy + ull(dy + 1) * (dx - 1) / 2;
  35. 				x += dx, y -= dy;
  36. 			}
  37. 			if (y <= w) break;
  38. 			while (true) {
  39. 				pop (), ux = dx, uy = dy, top (dx, dy);
  40. 				if (outside (x + dx, y - dy)) break;
  41. 			}
  42. 			while (true) {
  43. 				mx = ux + dx, my = uy + dy;
  44. 				if (!outside (x + mx, y - my)) {
  45. 					if (cut_off (x + mx, dx, dy)) break;
  46. 					ux = mx, uy = my;
  47. 				} else push (dx = mx, dy = my);
  48. 			}
  49. 		}
  50. 		for (y --; y; y --) ret += n / y;
  51. 		return stac :: qr = 0, ret * 2 - v * v;
  52. 	}
  53. }
  54.  
  55. void print (uLL v) {
  56. 	static char str[105]; int len;
  57. 	if (!v) str[++ len] = '0';
  58. 	while (v) str[++ len] = v % 10 + '0', v /= 10;
  59. 	while (len) putchar (str[len --]);
  60. 	putchar ('\n');
  61. }
  62.  
  63. int main(){
  64. 	ull n;
  65. 	for (scanf ("%llu", &n); scanf ("%llu", &n) != EOF; print (ds :: solve (n)));
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PagVPQ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!