Advertisement
trafik

Untitled

Oct 3rd, 2022
781
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1.  
  2. void solve() {
  3.     int n; cin >> n;
  4.     vi a(n); cin >> a;
  5.     int k = *max_element(all(a)) + 1;
  6.  
  7.     vector<vector<int>> del(k);
  8.     for (int i = 1; i < k; ++i) {
  9.         for (int j = i; j < k; j += i) {
  10.             del[j].push_back(i);
  11.         }
  12.     }
  13.     vector<int> cnt(k);
  14.     for (int i = 0; i < n; ++i) {
  15.         for (int j : del[a[i]]) {
  16.             cnt[j]++;
  17.         }
  18.     }
  19.     vector<long long> ans(k);
  20.     for (int i = 0; i < k; ++i) {
  21.         ans[i] = 1ll * cnt[i] * (cnt[i] - 1) / 2;
  22.     }
  23.     for (int i = k - 1; i >= 0; --i) {
  24.         for (int j : del[i]) {
  25.             if (j != i) {
  26.                 ans[j] -= ans[i];
  27.             }
  28.         }
  29.     }
  30.     cout << ans[1];
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement