fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <climits>
  12. #include <iomanip>
  13. #include <cstdio>
  14. #define ll   long long int
  15. #define MOD 1000000007
  16. #define inf  20000000000000
  17. #define eps  0.0000000000001
  18. using namespace std ; 
  19. vector<int> divi[1000001] ;  
  20.  
  21. ll Mul[1000001] ; 
  22. ll ans[1000001] ;  
  23. int arr[100001]  ; 
  24. int main()
  25. {
  26.    ios::sync_with_stdio(false);cin.tie(0) ;cout.tie(0) ;
  27.    int n  ;  
  28.    cin>>n ;     
  29.  
  30.  
  31.  
  32.    for(int i  = 2 ;  i <=  1000000 ; ++i)
  33.    {
  34.       ll j  =  i ;   
  35.       while(j <= 1000000)
  36.       {
  37.          divi[j].push_back(i) ;  
  38.          j +=  i  ;  
  39.       }
  40.    }
  41.  
  42.     for(ll  i =  0 ;  i < n  ; ++i)
  43.     {
  44.         cin>>arr[i] ;   
  45.  
  46.         for(ll u : divi[arr[i]])
  47.         {
  48.            Mul[u]++  ; 
  49.         }
  50.         Mul[1]++;
  51.  
  52.     }
  53.      ll zz = 0  ; 
  54.     for(ll i  = 1000000 ;  i >= 2 ;  --i)
  55.     {
  56.       if(Mul[i] < 3)
  57.         continue ;  
  58.  
  59.       ll j   =  i * 2    ; 
  60.       ll rem = 0  ;  
  61.       while(j <= 1000000)
  62.       {
  63.          rem += ans[j] ;  
  64.          j+= i ;  
  65.       }
  66.       ans[i]  =  (Mul[i]  * (Mul[i]  - 1) * (Mul[i]  -2))/6 - rem  ;
  67.       zz += ans[i] ;   
  68.  
  69.     }
  70.     cout<<(Mul[1]  * (Mul[1]  - 1) * (Mul[1]  -2))/6 - zz   ;  
  71.  
  72.  
  73.  return  0  ;
  74. } 
  75.  
  76.  
Success #stdin #stdout 1.17s 96128KB
comments (?)
stdin
copy 
4
1 2 3 4
stdout
copy 
4
https://ideone.com/zmxQ9u
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!