fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() 
  5. {
  6. 	// freopen("bhlt_bai1.inp", "r", stdin);
  7. 	// freopen("bhlt_bai1.out", "w", stdout);
  8.     long long n, x, a[1000005], b[1000005], r[1000005], mx = 0; cin >> n;
  9. 	memset(r, 0, sizeof(r));
  10. 	long long s1 = 0, s2 = 0;
  11.     for(int i = 0; i < n; i++){
  12.       cin >> x;
  13.       s1 += x;
  14.       s2 += x * x;
  15.       a[x]++;
  16.       mx = max(mx, x);
  17.     }
  18.     s1 = (s1 * s1 - s2) / 2;
  19.     for(int i = 1; i <= mx; i++){
  20.       for(int j = i; j <= mx; j += i){
  21.         b[i] += a[j];
  22.       }
  23.     }
  24.  
  25.     for(int i = mx; i > 0; i--){
  26.     	r[i] = b[i] * (b[i] - 1) / 2;
  27.       for(int j = i + i; j <= mx; j+=i){
  28.         r[i] -= r[j];
  29.       }
  30.  
  31.     }
  32.     cout << s1 << " ";
  33.     long long res = 0;
  34.     for(int i = 1; i <= mx; i++) res +=  r[i] * s1  / i;
  35.     cout << res << endl;
  36.     for(int i = 0; i <= mx; i++) cout << r[i] << " ";
  37.  
  38.  
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0.01s 15156KB
comments (?)
stdin
copy 
5
10 7 4 3 3
stdout
copy 
273 2411
0 8 1 1 0 0 0 0 0 0 0
https://ideone.com/nymKce
language:
C++14 (clang 8.0)
created:
7 days 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!