Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <cstring>
- #include <cctype>
- #include <ctime>
- #include <iostream>
- #include <iomanip>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <stack>
- #include <queue>
- #include <deque>
- #include <string>
- #include <vector>
- #include <bitset>
- using namespace std;
- const int M = 1001;
- const int N = 1000100;
- std::bitset <N + 10> ar;
- std::vector <int> v[1010];
- void Sieve(){
- ar.reset();
- for (int i = 2; i < N; i++) ar[i] = true;
- for (int i = 4; i < N; i += 2) ar[i] = false;
- int i = 3;
- for (int d = 0; d <= 1010; d++){
- int dif = i << 1;
- for (int j = (i + dif); j < N; j += dif) ar[j] = false;
- i += 2;
- while (!ar[i]) i += 2;
- }
- }
- int prev_prime(int x){
- int i = (x - 1);
- while (!ar[i]) i--;
- return (i);
- }
- int next_prime(int x){
- int i = (x + 1);
- while (!ar[i]) i++;
- return (i);
- }
- int gcd(int a, int b){
- if (a == 0) return (b);
- else return (gcd((b % a), a));
- }
- int bigmod(unsigned long long int x, unsigned long long int y){
- if (y == 0) return (1 % M);
- if (y == 1) return (x % M);
- unsigned long long int z = bigmod(x, y / 2);
- if ((y % 2) == 0) return ((z * z) % M);
- else return ((((z * z) % M) * x) % M);
- }
- int Piggy_Scheme(int x){
- if (x < 3) return (1000 - x);
- unsigned long long int t = x;
- unsigned long long int a = (unsigned long long int)prev_prime(x) * t;
- unsigned long long int b = next_prime(x);
- return (bigmod(a, b));
- }
- int main(){
- Sieve();
- int t, p, q, d, k;
- for (int i = 0; i < 1010; i++) v[i].clear();
- for (int i = 0; i <= 1000000; i++){
- int x = Piggy_Scheme(i);
- v[x].push_back(i);
- }
- scanf("%d", &t);
- for (int line = 1; line <= t; line++){
- scanf("%d %d %d %d", &p, &q, &d, &k);
- int c = 0, len = v[p].size(), len2 = v[q].size();
- for (int i = 0; i < len; i++){
- int x = v[p][i];
- for (int j = 0; j < len2; j++){
- int y = v[q][j];
- if (abs(x - y) <= d) c++;
- if (abs(x - y) <= d) printf("%d %d\n", x, y);
- }
- }
- printf("%d %d\n", k, c);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement