Advertisement
palmerstone

Untitled

Oct 29th, 2011
428
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.05 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4. #include <ctype.h>
  5.  
  6. long long int ar[100], ar2[100], ar3[100], ar4[100];
  7.  
  8. long long int power(long long int x, long long int n)
  9. {
  10. long long int z = 1;
  11. if (n == 0) return 1;
  12. else if (n == 1) return x;
  13. else if (n % 2 == 0) z = (power(x, (n / 2)) * power(x, (n / 2)));
  14. else z = x * power(x, ((n - 1) / 2)) * power(x, ((n - 1) / 2));
  15. return z;
  16. }
  17.  
  18. long long int Binary_Count(int a)
  19. {
  20. int i, j, l;
  21. long long int x, y, z;
  22.  
  23. l = 0, x = a;
  24. for (i = 0; ;i++)
  25. {
  26. if (x <= 0) break;
  27. if (ar2[i + 1] > x)
  28. {
  29. if (x == 1)
  30. {
  31. ar3[l] = 1;
  32. ar4[l++] = 0;
  33. break;
  34. }
  35. x = x - ar2[i];
  36. ar3[l] = ar2[i];
  37. ar4[l++] = i;
  38. i = 0;
  39. }
  40. }
  41.  
  42. y = a, x = 0;
  43. for (i = 0; i < l; i++) x += ar[ar4[i]];
  44. for (i = 0; i < l; i++)
  45. {
  46. y = y - ar3[i];
  47. x += y;
  48. }
  49.  
  50. return x;
  51. }
  52.  
  53. int main()
  54. {
  55. int a, b, t, i, j;
  56. long long int c, d, x, y, z;
  57. char str[100];
  58.  
  59. ar[0] = 1, ar[1] = 2, ar2[0] = 1, ar2[1] = 2;
  60. for (i = 2; i <= 33; i++)
  61. {
  62. ar[i] = (2 * (ar[i - 1] - 1)) + power(2, (i - 1)) + 1;
  63. ar2[i] = power(2, i);
  64. }
  65.  
  66. for (t = 1; ;t++)
  67. {
  68. a = 0, b = 0, gets(str);
  69. for (j = 0; str[j] != 0; j++)
  70. {
  71. if (isdigit(str[j])) a = (a * 10) + str[j] - 48;
  72. else break;
  73. }
  74. j++;
  75. for (; str[j] != 0; j++)
  76. {
  77. if (isdigit(str[j])) b = (b * 10) + str[j] - 48;
  78. else break;
  79. }
  80. if (a == 0 && b == 0) break;
  81.  
  82. x = Binary_Count(a), y = Binary_Count(b);
  83. z = y - x;
  84. x = a;
  85. for (; ;)
  86. {
  87. c = x / 2;
  88. d = x % 2;
  89. if (d == 1) z++;
  90. x = c;
  91. if (c == 0) break;
  92. }
  93. printf("Case %d: %lld\n", t, z);
  94. }
  95. return 0;
  96. }
  97.  
  98.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement