fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 200000;
  5.  
  6. int solve(const vector<int>& a, int y) {
  7.     int mx = 0;
  8.     for (int num : a) {
  9.         mx = max(mx, num);
  10.     }
  11.  
  12.     vector<int> f(mx + 1, 0);
  13.     for (int num : a) {
  14.         f[num]++;
  15.     }
  16.  
  17.     vector<int> u(mx + 1, 0);
  18.     for (int i = 1; i <= mx; i++) {
  19.         for (int j = i; j <= mx; j += i) {
  20.             u[i] += f[j];
  21.         }
  22.     }
  23.  
  24.     vector<long long> m(mx + 1, 0);
  25.     for (int i = 1; i <= mx; i++) {
  26.         if (u[i] >= 2) {
  27.             m[i] = (long long)u[i] * (u[i] - 1) / 2; // nC2
  28.         }
  29.     }
  30.  
  31.     vector<long long> g(mx + 1, 0);
  32.  
  33.     for (int i = mx; i >= 1; i--) {
  34.         g[i] = m[i];
  35.  
  36.         for (int j = 2 * i; j <= mx; j += i) {
  37.             g[i] -= g[j];
  38.         }
  39.     }
  40.     return (int)max(0LL, g[y]);
  41. }
  42.  
  43. int main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.  
  47.     int t;
  48.     cin >> t;
  49.  
  50.     while (t--) {
  51.         int n, y;
  52.         cin >> n >> y;
  53.  
  54.         vector<int> a(n);
  55.         for (int i = 0; i < n; i++) {
  56.             cin >> a[i];
  57.         }
  58.         cout << solve(a, y) << "\n";
  59.     }
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
1
5 2
2 4 6 8 10
stdout
copy 
9
https://ideone.com/ppXSmV
language:
C++14 (gcc 8.3)
created:
1 day 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!