fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<int , pair<int , int>>
  10. #define lii pair<long long , pair<int , int>>
  11. #define li pair<long long , int>
  12. #define db double
  13. #define onBit(mask , i) (mask | (1 << i))
  14. #define offBit(mask , i) (mask & (~(1 << i)))
  15.  
  16. const int N = 1e7 + 7;
  17. int n = 0 , m , k;
  18. int a[N];
  19.  
  20. long long mul_mod(long long a , long long b , long long m){
  21.     return ((a % m) * (b % m)) % m;
  22. }
  23.  
  24. long long Pow_Mod(long long a , long long b , long long m){
  25.     long long res = 1;
  26.     while (b){
  27.         if (b % 2 == 1){
  28.             res *= a;
  29.             res %= m;
  30.         }
  31.  
  32.         b /= 2;
  33.         a *= a;
  34.         a %= m;
  35.     }
  36.     return res;
  37. }
  38.  
  39. bool miller_test(long long a, long long s, long long d, long long n){
  40.     long long x = Pow_Mod(a, d, n);
  41.     if (x == 1 || x == n - 1) return true;
  42.     for (int i = 1; i < s; i++) {
  43.         x = mul_mod(x, x, n);
  44.         if (x == n - 1) return true;
  45.     }
  46.     return false;
  47. }
  48.  
  49. bool isPrime(long long n){
  50.     if (n < 2) return false;
  51.     for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29})
  52.         if (n == p) return true;
  53.         else if (n % p == 0) return false;
  54.  
  55.     long long d = n - 1, s = 0;
  56.     while ((d & 1) == 0) {
  57.         d >>= 1;
  58.         s++;
  59.     }
  60.  
  61.     for (long long a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
  62.         if (a % n == 0) continue;
  63.         if (!miller_test(a, s, d, n)) return false;
  64.     }
  65.     return true;
  66. }
  67.  
  68. void inp(){
  69.     cin >> m >> k;
  70.     for (int i = 1 ; i <= m ; ++i){
  71.         int x;
  72.         cin >> x;
  73.         if (isPrime(x)){
  74.             ++n;
  75.             a[n] = x;
  76.         }
  77.     }
  78.     sort(a + 1 , a + n + 1);
  79. }
  80.  
  81. void solve(){
  82.     long long res = 0;
  83.     int i = 1 , j = 1;
  84.     while (i <= n){
  85.         while (j < n && a[j + 1] - a[i] <= k) ++j;
  86.         res += (1LL * j - 1LL * i);
  87.         ++i;
  88.         if (j < i) j = i;
  89.     }
  90.     cout << res;
  91. }
  92.  
  93.  
  94. int main(){
  95.     if (fopen("cau2.inp" , "r")){
  96.         freopen("cau2.inp" , "r" , stdin);
  97.         freopen("cau2.out" , "w" , stdout);
  98.     }
  99.     faster;
  100.     inp();
  101.     solve();
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/D3x39d
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

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!