Advertisement
palmerstone

Untitled

May 3rd, 2012
468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.27 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <cctype>
  6. #include <ctime>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <algorithm>
  10. #include <map>
  11. #include <set>
  12. #include <stack>
  13. #include <queue>
  14. #include <deque>
  15. #include <string>
  16. #include <vector>
  17. #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. const int M = 1001;
  22. const int N = 1000100;
  23. std::bitset <N + 10> ar;
  24. std::vector <int> v[1010];
  25.  
  26. void Sieve(){
  27. ar.reset();
  28. for (int i = 2; i < N; i++) ar[i] = true;
  29. for (int i = 4; i < N; i += 2) ar[i] = false;
  30.  
  31. int i = 3;
  32. for (int d = 0; d <= 1010; d++){
  33. int dif = i << 1;
  34. for (int j = (i + dif); j < N; j += dif) ar[j] = false;
  35. i += 2;
  36. while (!ar[i]) i += 2;
  37. }
  38. }
  39.  
  40. int prev_prime(int x){
  41. int i = (x - 1);
  42. while (!ar[i]) i--;
  43. return (i);
  44. }
  45.  
  46. int next_prime(int x){
  47. int i = (x + 1);
  48. while (!ar[i]) i++;
  49. return (i);
  50. }
  51.  
  52. int gcd(int a, int b){
  53. if (a == 0) return (b);
  54. else return (gcd((b % a), a));
  55. }
  56.  
  57. int bigmod(unsigned long long int x, unsigned long long int y){
  58. if (y == 0) return (1 % M);
  59. if (y == 1) return (x % M);
  60. unsigned long long int z = bigmod(x, y / 2);
  61. if ((y % 2) == 0) return ((z * z) % M);
  62. else return ((((z * z) % M) * x) % M);
  63. }
  64.  
  65. int Piggy_Scheme(int x){
  66. if (x < 3) return (1000 - x);
  67. unsigned long long int t = x;
  68. unsigned long long int a = (unsigned long long int)prev_prime(x) * t;
  69. unsigned long long int b = next_prime(x);
  70. return (bigmod(a, b));
  71. }
  72.  
  73. int main(){
  74. Sieve();
  75. int t, p, q, d, k;
  76. for (int i = 0; i < 1010; i++) v[i].clear();
  77. for (int i = 0; i <= 1000000; i++){
  78. int x = Piggy_Scheme(i);
  79. v[x].push_back(i);
  80. }
  81.  
  82. scanf("%d", &t);
  83. for (int line = 1; line <= t; line++){
  84. scanf("%d %d %d %d", &p, &q, &d, &k);
  85. int c = 0, len = v[p].size(), len2 = v[q].size();
  86. for (int i = 0; i < len; i++){
  87. int x = v[p][i];
  88. for (int j = 0; j < len2; j++){
  89. int y = v[q][j];
  90. if (abs(x - y) <= d) c++;
  91. if (abs(x - y) <= d) printf("%d %d\n", x, y);
  92. }
  93. }
  94.  
  95. printf("%d %d\n", k, c);
  96. }
  97.  
  98. return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement