fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,a[100005],t[100005],t2[100005],uc[100005],kq = 0,s,s2;
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8.     freopen("Basohang.inp", "r", stdin);
  9.     freopen("Basohang.out", "w", stdout);
  10.     cin >> n;
  11.     for(int i = 1; i <= n; i++)
  12.     cin >> a[i];
  13.     if(n <= 1000)
  14.     {
  15.         for(int i = 2; i < n; i++)
  16.         {
  17.             s = s2 = 0;
  18.             for(int j = i - 1; j >= 1; j--)
  19.                 s += (a[i] % a[j] == 0);
  20.             for(int j = i + 1; j <= n; j++)
  21.                 s2 += (a[j] % a[i] == 0);
  22.             kq += s*s2;
  23.         }
  24.         cout << kq;
  25.         return 0;
  26.     }
  27.     else
  28.     {
  29.         kq = 0;
  30.         for(int i = 2; i <= n; i++)
  31.         {
  32.             for(int j = 1; j <= sqrt(a[i]); j++)
  33.             {
  34.                 if(a[i] % j == 0)
  35.                 {
  36.                     uc[j]++;
  37.                     if(a[i]/j != j)
  38.                         uc[a[i]/j]++;
  39.                 }
  40.             }
  41.         }
  42.         t2[a[1]]++;
  43.         for(int i = 2; i < n; i++)
  44.         {
  45.             for(int j = 1; j <= sqrt(a[i]); j++)
  46.             {
  47.                 if(a[i] % j == 0)
  48.                 {
  49.                     uc[j]--;
  50.                     if(a[i]/j != j)
  51.                         uc[a[i]/j]--;
  52.                 }
  53.             }
  54.             for(int j = 1; j <= sqrt(a[i]); j++)
  55.             {
  56.                 if(a[i] % j == 0)
  57.                 {
  58.                     kq += uc[a[i]] * t2[j];
  59.                     if(a[i]/j != j)
  60.                         kq += uc[a[i]] * t2[a[i]/j];
  61.                 }
  62.             }
  63.             t2[a[i]]++;
  64.         }
  65.         cout << kq;
  66.         return 0;
  67.     }
  68. }
  69.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z7LBFH
language:
C++14 (gcc 8.3)
created:
6 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!