fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <vector>
  5. #include <iostream>
  6. #include <math.h>
  7. #define FOR(a,b,c)		for (s32(a)=(b);(a)<(s32)(c);(a)++)
  8. using namespace std;
  9. typedef int						s32;
  10. typedef long long int			s64;
  11. typedef long long int   		Int;
  12.  
  13. /*
  14. 	Return sqrt(n). Ex:10->3
  15. */
  16. s64 Sqrt(s64 n)
  17. {
  18.   s64 s, t;
  19.   if (n <= 0) return 0;
  20.   s = 1;  t = n;
  21.   while (s < t) {  s <<= 1;  t >>= 1;  }
  22.   do {
  23.     t = s;
  24.     s = (n / s + s) >> 1;
  25.   } while (s < t);
  26.   return t;
  27. }
  28.  
  29. s64 Naive(s64 n) {
  30. 	s64 r = 0;
  31. 	for (s64 a = 1; a <=n; a++) {
  32. 		s64 s2 = (2 * a - 1)*(2 * a - 1) + 8 * n;
  33. 		s64 s = Sqrt(s2);
  34. 		if (s * s != s2 || s % 2 == 0) continue;
  35. 		s64 m = (-2 * a + 1 + s) / 2;
  36. 		if (m != 1) {
  37. //			cout << a << " " << m << endl;
  38. 			r += a;
  39. 		}
  40. 	}
  41. 	return r;
  42. }
  43.  
  44. s64 Check(s64 n, s64 p, s64 q) {
  45. 	s64 m = p, a;
  46. 	if ((2 * n / m + 1 - m) % 2 == 0) {
  47. 		a = (2 * n / m + 1 - m) / 2;
  48. 		if (a >= 1 && m >= 2) {
  49. //			cout << a << " " << m << endl;
  50. 			return a;
  51. 		}
  52. 	}
  53. 	return 0;
  54. }
  55.  
  56. s64 Smart(s64 n) {
  57. 	s64 p, a, m, r = 0;
  58. 	for (p = 2; p * p <= 2 * n; p ++) {
  59. 		if ((n * 2) % p != 0) continue;
  60. 		r += Check(n, p, 2 * n / p);
  61. 		r += Check(n, 2 * n / p, p);
  62. 	}
  63. 	return r;
  64. }
  65.  
  66. int main(int argc, char *argv[])
  67. {
  68.     cout.precision(16);
  69.     s64 n;
  70. 	cin >> n;
  71.  
  72. 	double r0 = Smart(n);
  73. 	cout << r0 << endl;
  74.  
  75. //	double r2 = Naive(n);
  76. //	cout << r2 << endl;
  77. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
10000000000
stdout
copy 
2505942121
https://ideone.com/AVLGnz
「ステップ・アップ・サム」問題 Kawazoeのコード
language:
C++ (gcc 8.3)
created:
8 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!