fork download
copy 
  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 , _max = 0;
  18. int a[N];
  19. long long ans = 0 , pre[N];
  20.  
  21. long long mul_mod(long long a , long long b , long long m){
  22.     return ((a % m) * (b % m)) % m;
  23. }
  24.  
  25. long long Pow_Mod(long long a , long long b , long long m){
  26.     long long res = 1;
  27.     while (b){
  28.         if (b % 2 == 1){
  29.             res *= a;
  30.             res %= m;
  31.         }
  32.  
  33.         b /= 2;
  34.         a *= a;
  35.         a %= m;
  36.     }
  37.     return res;
  38. }
  39.  
  40. bool miller_test(long long a, long long s, long long d, long long n){
  41.     long long x = Pow_Mod(a, d, n);
  42.     if (x == 1 || x == n - 1) return true;
  43.     for (int i = 1; i < s; i++) {
  44.         x = mul_mod(x, x, n);
  45.         if (x == n - 1) return true;
  46.     }
  47.     return false;
  48. }
  49.  
  50. bool isPrime(long long n){
  51.     if (n < 2) return false;
  52.     for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29})
  53.         if (n == p) return true;
  54.         else if (n % p == 0) return false;
  55.  
  56.     long long d = n - 1, s = 0;
  57.     while ((d & 1) == 0) {
  58.         d >>= 1;
  59.         s++;
  60.     }
  61.  
  62.     for (long long a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
  63.         if (a % n == 0) continue;
  64.         if (!miller_test(a, s, d, n)) return false;
  65.     }
  66.     return true;
  67. }
  68.  
  69. void inp(){
  70.     cin >> m >> k;
  71.     for (int i = 1 ; i <= m ; ++i){
  72.         int x;
  73.         cin >> x;
  74.         if (isPrime(x)){
  75.             ++n;
  76.             a[n] = x;
  77.             ++pre[x];
  78.             _max = max(_max , x);
  79.         }
  80.     }
  81.     for (int i = 1 ; i <= _max ; ++i){
  82.         ans += pre[i] * (pre[i] - 1LL) / 2;
  83.         pre[i] += pre[i - 1];
  84.     }
  85. }
  86.  
  87. void solve(){
  88.     for (int i = 1 ; i <= n ; ++i){
  89.         ans += pre[min(_max , a[i] + k)] - pre[a[i]];
  90.     }
  91.     cout << ans;
  92. }
  93.  
  94.  
  95. int main(){
  96.     if (fopen("cau2.inp" , "r")){
  97.         freopen("cau2.inp" , "r" , stdin);
  98.         freopen("cau2.out" , "w" , stdout);
  99.     }
  100.     faster;
  101.     inp();
  102.     solve();
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BSj2wO
language:
C++14 (gcc 8.3)
created:
16 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!